#include <bits/stdc++.h>
#define DBG(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;

struct Node {
    int val;
    Node *left, *right;

    Node() : left(NULL), right(NULL) {}

    Node(int val) : val(val), left(NULL), right(NULL) {}
};

enum StackState {
    AFTER_PUSH_ROOT = 0,
    AFTER_PUSH_LEFT = 1,
    AFTER_PUSH_RIGHT = 2,
};

void dfs_pre_order(Node *root, vector<int> &ret) {
    ret.push_back(root->val);
    if (root->left) dfs_pre_order(root->left, ret);
    if (root->right) dfs_pre_order(root->right, ret);
}

void dfs_in_order(Node *root, vector<int> &ret) {
    if (root->left) dfs_in_order(root->left, ret);
    ret.push_back(root->val);
    if (root->right) dfs_in_order(root->right, ret);
}

void dfs_post_order(Node *root, vector<int> &ret) {
    if (root->left) dfs_post_order(root->left, ret);
    if (root->right) dfs_post_order(root->right, ret);
    ret.push_back(root->val);
}

void pre_order(Node *root, vector<int> &ret) {
    stack<pair<Node *, StackState>> stk;
    stk.push(pair<Node *, StackState>(root, AFTER_PUSH_ROOT));
    while (!stk.empty()) {
        pair<Node *, StackState> &top = stk.top();
        switch (top.second) {
            case AFTER_PUSH_ROOT:
                ret.push_back(top.first->val);
                if (top.first->left) stk.push(pair<Node *, StackState>(top.first->left, AFTER_PUSH_ROOT));
                top.second = AFTER_PUSH_LEFT;
                break;
            case AFTER_PUSH_LEFT:
                if (top.first->right) stk.push(pair<Node *, StackState>(top.first->right, AFTER_PUSH_ROOT));
                top.second = AFTER_PUSH_RIGHT;
                break;
            case AFTER_PUSH_RIGHT:
                stk.pop();
                break;
        }
    }
}

void in_order(Node *root, vector<int> &ret) {
    stack<pair<Node *, StackState>> stk;
    stk.push(pair<Node *, StackState>(root, AFTER_PUSH_ROOT));
    while (!stk.empty()) {
        pair<Node *, StackState> &top = stk.top();
        switch (top.second) {
            case AFTER_PUSH_ROOT:
                if (top.first->left) stk.push(pair<Node *, StackState>(top.first->left, AFTER_PUSH_ROOT));
                top.second = AFTER_PUSH_LEFT;
                break;
            case AFTER_PUSH_LEFT:
                ret.push_back(top.first->val);
                if (top.first->right) stk.push(pair<Node *, StackState>(top.first->right, AFTER_PUSH_ROOT));
                top.second = AFTER_PUSH_RIGHT;
                break;
            case AFTER_PUSH_RIGHT:
                stk.pop();
                break;
        }
    }
}

void post_order(Node *root, vector<int> &ret) {
    stack<pair<Node *, StackState>> stk;
    stk.push(pair<Node *, StackState>(root, AFTER_PUSH_ROOT));
    while (!stk.empty()) {
        pair<Node *, StackState> &top = stk.top();
        switch (top.second) {
            case AFTER_PUSH_ROOT:
                if (top.first->left) stk.push(pair<Node *, StackState>(top.first->left, AFTER_PUSH_ROOT));
                top.second = AFTER_PUSH_LEFT;
                break;
            case AFTER_PUSH_LEFT:
                if (top.first->right) stk.push(pair<Node *, StackState>(top.first->right, AFTER_PUSH_ROOT));
                top.second = AFTER_PUSH_RIGHT;
                break;
            case AFTER_PUSH_RIGHT:
                ret.push_back(top.first->val);
                stk.pop();
                break;
        }
    }
}

Node *get_tree(int num) {
    Node *root = new Node(random());
    vector<Node *> nodes;
    nodes.push_back(root);

    for (int i = 0; i < num; i++) {
        unsigned int pos = random() * random() * random() % nodes.size();
        if (nodes[pos]->left == NULL && nodes[pos]->right == NULL) {
            if (random() % 2 == 0) {
                nodes[pos]->left = new Node(random());
                nodes.push_back(nodes[pos]->left);
            } else {
                nodes[pos]->right = new Node(random());
                nodes.push_back(nodes[pos]->right);
            }
        } else if (nodes[pos]->left) {
            nodes[pos]->right = new Node(random());
            nodes.push_back(nodes[pos]->right);
        } else {
            nodes[pos]->left = new Node(random());
            nodes.push_back(nodes[pos]->left);
        }
        if (nodes[pos]->left && nodes[pos]->right) {
            nodes.erase(nodes.begin() + pos);
        }
    }

    return root;
}

void free_tree(Node *root) {
    if (root->left) free_tree(root->left);
    if (root->right) free_tree(root->right);
    delete root;
}

void test_pre_order() {
    Node *tree = get_tree(100000);
    vector<int> dfs_ret, ret;

    dfs_pre_order(tree, dfs_ret);
    pre_order(tree, ret);
    assert(dfs_ret == ret);

    free_tree(tree);
}

void test_in_order() {
    Node *tree = get_tree(100000);
    vector<int> dfs_ret, ret;

    dfs_in_order(tree, dfs_ret);
    in_order(tree, ret);
    assert(dfs_ret == ret);

    free_tree(tree);
}

void test_post_order() {
    Node *tree = get_tree(100000);
    vector<int> dfs_ret, ret;

    dfs_post_order(tree, dfs_ret);
    post_order(tree, ret);
    assert(dfs_ret == ret);

    free_tree(tree);
}

int main(int argc, char **argv) {
    srand(time(NULL));

    test_pre_order();
    test_in_order();
    test_post_order();

    return 0;
}

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size() + nums2.size();
        if (n % 2 == 1)
            return kth(nums1, 0, nums2, 0, n / 2 + 1);
        else
            return (kth(nums1, 0, nums2, 0, n / 2) + kth(nums1, 0, nums2, 0, n / 2 + 1)) / 2.0;
    }
    int kth(vector<int> &nums1, int n1, vector<int> &nums2, int n2, int k) {
        if (nums1.size() - n1 > nums2.size() - n2)
            return kth(nums2, n2, nums1, n1, k);
        if (nums1.size() - n1 == 0)
            return nums2[n2 + k - 1];
        if (k == 1)
            return min(nums1[n1], nums2[n2]);
        
        int p = min(k / 2, int(nums1.size() - n1));
        if (nums1[n1 + p - 1] < nums2[n2 + p - 1])
            return kth(nums1, n1 + p, nums2, n2, k - p);
        else
            return kth(nums1, n1, nums2, n2 + p, k - p);
    }
};

#include <cstdio>
#include <cstring>
#include <cstdlib>

#include <time.h>
#include <unistd.h>
#include <signal.h>

using namespace std;

void handle(int num) {
    printf("signal num: %d\n", num);
    sleep(5);
    printf("sleep over\n");
}

int main(int argc, char *argv[]) {
    for (int i = 1; i < argc;) {
        if (strcmp(argv[i], "--handle") == 0) {
            signal(atoi(argv[i + 1]), handle);
            i += 2;
            continue;
        }
        i++;
    }

    printf("pid: %d\n", getpid());

    while (true) {
        printf("%d\n", time(NULL));
        sleep(1);
    }
    return 0;
}

#include <cstdio>
#include <cstring>
#include <cstdlib>

#include <signal.h>
#include <time.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/wait.h>

using namespace std;

void handle(int num) {
    printf("signal num: %d\n", num);
}

int main(int argc, char *argv[]) {
    int options = 0;
    bool divide_zero = false;
    bool invalid_memory = false;

    for (int i = 1; i < argc;) {
        if (strcmp(argv[i], "--WUNTRACED") == 0) {
            options |= WUNTRACED;
            i++;
            continue;
        } else if (strcmp(argv[i], "--WNOHANG") == 0) {
            options |= WNOHANG;
            i++;
            continue;
        } else if (strcmp(argv[i], "--WCONTINUED") == 0) {
            options |= WCONTINUED;
            i++;
            continue;
        } else if (strcmp(argv[i], "--handle") == 0) {
            signal(atoi(argv[i + 1]), handle);
            i += 2;
            continue;
        } else if (strcmp(argv[i], "--divide-zero") == 0) {
            divide_zero = true;
            i++;
            continue;
        } else if (strcmp(argv[i], "--invalid-memory") == 0) {
            invalid_memory = true;
            i++;
            continue;
        }
        i++;
    }

    pid_t cpid, w;
    int status;

    cpid = fork();
    if (cpid == -1) {
        fprintf(stderr, "fork failed\n");
        exit(EXIT_FAILURE);
    }

    if (cpid == 0) {
        printf("Child PID is %ld\n", (long) getpid());
        if (divide_zero) {
            int x = 1337;
            int y = x / 0;
            printf("%d\n", y);
        }
        if (invalid_memory) {
            *(int *) 0 = 1337;
        }
        while (true) {
            printf("time: %d\n", time(NULL));
            sleep(1);
        }
    } else {
        printf("Father PID is %ld\n", (long) getpid());
        do {
            w = waitpid(cpid, &status, options);
            printf("w: %d, WIFEXITED: %d, WIFSIGNALED: %d, WIFSTOPPED: %d, WIFCONTINUED: %d\n",
                   w, WIFEXITED(status), WIFSIGNALED(status), WIFSTOPPED(status), WIFCONTINUED(status));
            if (w == 0) {
                continue;
            }
            if (w == -1) {
                fprintf(stderr, "waitpid error\n");
                exit(EXIT_FAILURE);
            }
            if (WIFEXITED(status)) {
                printf("exited, status=%d\n", WEXITSTATUS(status));
            } else if (WIFSIGNALED(status)) {
                printf("killed by signal %d\n", WTERMSIG(status));
            } else if (WIFSTOPPED(status)) {
                printf("stopped by signal %d\n", WSTOPSIG(status));
            } else if (WIFCONTINUED(status)) {
                printf("continued\n");
            }
        } while ((!WIFEXITED(status) && !WIFSIGNALED(status)) || w == 0);
        exit(EXIT_SUCCESS);
    }
}

#include <bits/stdc++.h>
#include <unistd.h>
#include <sys/resource.h>
#include <sys/time.h>

#define DBG(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;

double cpu_load(double start, double end, double used) {
    return used / (end - start) * 100;
}

double cpu_time_used_s() {
    rusage usage;
    getrusage(RUSAGE_SELF, &usage);
    return usage.ru_stime.tv_sec + double(usage.ru_stime.tv_usec) / 1000000 + usage.ru_utime.tv_sec + double(usage.ru_utime.tv_usec) / 1000000;
}

double get_time_s() {
    timeval tv;
    gettimeofday(&tv, NULL);
    return tv.tv_sec + double(tv.tv_usec) / 1000000;
}

int main(int argc, char **argv) {
    double start = get_time_s();

    srand(time(NULL));
    int x = rand();
    for (int i = 0; i < 300000000; i++) {
        x ^= rand();
        x |= rand();
        x &= ~rand();
    }

    sleep(5);

    double end = get_time_s();
    double real_time_used = end - start;
    double cpu_time_used = cpu_time_used_s();

    printf("start: %.3fs, end: %.3fs\n"
           "real_time_used: %.3f\n"
           "cpu_time_used: %.3fs, cpu_load: %.3f%%\n",
           start, end, real_time_used, cpu_time_used, cpu_load(start, end, cpu_time_used));

    return 0;
}

/* Object types */
#define REDIS_STRING 0
#define REDIS_LIST 1
#define REDIS_SET 2
#define REDIS_ZSET 3
#define REDIS_HASH 4

/* Objects encoding. Some kind of objects like Strings and Hashes can be
 * internally represented in multiple ways. The 'encoding' field of the object
 * is set to one of this fields for this object. */
#define REDIS_ENCODING_RAW 0     /* Raw representation */
#define REDIS_ENCODING_INT 1     /* Encoded as integer */
#define REDIS_ENCODING_HT 2      /* Encoded as hash table */
#define REDIS_ENCODING_ZIPMAP 3  /* Encoded as zipmap */
#define REDIS_ENCODING_LINKEDLIST 4 /* Encoded as regular linked list */
#define REDIS_ENCODING_ZIPLIST 5 /* Encoded as ziplist */
#define REDIS_ENCODING_INTSET 6  /* Encoded as intset */
#define REDIS_ENCODING_SKIPLIST 7  /* Encoded as skiplist */
#define REDIS_ENCODING_EMBSTR 8  /* Embedded sds string encoding */

typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:REDIS_LRU_BITS; /* lru time (relative to server.lruclock) */
    int refcount;
    void *ptr;
} robj;

typedef char *sds;

struct sdshdr {
    unsigned int len;
    unsigned int free;
    char buf[];
};

/* Append the specified binary-safe string pointed by 't' of 'len' bytes to the
 * end of the specified sds string 's'.
 *
 * After the call, the passed sds string is no longer valid and all the
 * references must be substituted with the new pointer returned by the call. */
sds sdscatlen(sds s, const void *t, size_t len) {
    struct sdshdr *sh;
    size_t curlen = sdslen(s);

    s = sdsMakeRoomFor(s,len);
    if (s == NULL) return NULL;
    sh = (void*) (s-(sizeof(struct sdshdr)));
    memcpy(s+curlen, t, len);
    sh->len = curlen+len;
    sh->free = sh->free-len;
    s[curlen+len] = '\0';
    return s;
}

/* Append the specified null termianted C string to the sds string 's'.
 *
 * After the call, the passed sds string is no longer valid and all the
 * references must be substituted with the new pointer returned by the call. */
sds sdscat(sds s, const char *t) {
    return sdscatlen(s, t, strlen(t));
}

/* Node, List, and Iterator are the only data structures used currently. */

typedef struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value;
} listNode;

typedef struct listIter {
    listNode *next;
    int direction;
} listIter;

typedef struct list {
    listNode *head;
    listNode *tail;
    void *(*dup)(void *ptr);
    void (*free)(void *ptr);
    int (*match)(void *ptr, void *key);
    unsigned long len;
} list;

/* Functions implemented as macros */
#define listLength(l) ((l)->len)
#define listFirst(l) ((l)->head)
#define listLast(l) ((l)->tail)
#define listPrevNode(n) ((n)->prev)
#define listNextNode(n) ((n)->next)
#define listNodeValue(n) ((n)->value)

#define listSetDupMethod(l,m) ((l)->dup = (m))
#define listSetFreeMethod(l,m) ((l)->free = (m))
#define listSetMatchMethod(l,m) ((l)->match = (m))

#define listGetDupMethod(l) ((l)->dup)
#define listGetFree(l) ((l)->free)
#define listGetMatchMethod(l) ((l)->match)

/* Prototypes */
list *listCreate(void);
void listRelease(list *list);
list *listAddNodeHead(list *list, void *value);
list *listAddNodeTail(list *list, void *value);
list *listInsertNode(list *list, listNode *old_node, void *value, int after);
void listDelNode(list *list, listNode *node);
listIter *listGetIterator(list *list, int direction);
listNode *listNext(listIter *iter);
void listReleaseIterator(listIter *iter);
list *listDup(list *orig);
listNode *listSearchKey(list *list, void *key);
listNode *listIndex(list *list, long index);
void listRewind(list *list, listIter *li);
void listRewindTail(list *list, listIter *li);
void listRotate(list *list);

typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;
} dictEntry;

typedef struct dictType {
    unsigned int (*hashFunction)(const void *key);
    void *(*keyDup)(void *privdata, const void *key);
    void *(*valDup)(void *privdata, const void *obj);
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);
    void (*keyDestructor)(void *privdata, void *key);
    void (*valDestructor)(void *privdata, void *obj);
} dictType;

/* This is our hash table structure. Every dictionary has two of this as we
 * implement incremental rehashing, for the old to the new table. */
typedef struct dictht {
    dictEntry **table;
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
} dictht;

typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    int iterators; /* number of iterators currently running */
} dict;

/* Add an element to the target hash table */
int dictAdd(dict *d, void *key, void *val)
{
    dictEntry *entry = dictAddRaw(d,key);

    if (!entry) return DICT_ERR;
    dictSetVal(d, entry, val);
    return DICT_OK;
}

/* Low level add. This function adds the entry but instead of setting
 * a value returns the dictEntry structure to the user, that will make
 * sure to fill the value field as he wishes.
 *
 * This function is also directly exposed to the user API to be called
 * mainly in order to store non-pointers inside the hash value, example:
 *
 * entry = dictAddRaw(dict,mykey);
 * if (entry != NULL) dictSetSignedIntegerVal(entry,1000);
 *
 * Return values:
 *
 * If key already exists NULL is returned.
 * If key was added, the hash entry is returned to be manipulated by the caller.
 */
dictEntry *dictAddRaw(dict *d, void *key)
{
    int index;
    dictEntry *entry;
    dictht *ht;

    if (dictIsRehashing(d)) _dictRehashStep(d);

    /* Get the index of the new element, or -1 if
     * the element already exists. */
    if ((index = _dictKeyIndex(d, key)) == -1)
        return NULL;

    /* Allocate the memory and store the new entry */
    ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
    entry = zmalloc(sizeof(*entry));
    entry->next = ht->table[index];
    ht->table[index] = entry;
    ht->used++;

    /* Set the hash entry fields. */
    dictSetKey(d, entry, key);
    return entry;
}

dictEntry *dictFind(dict *d, const void *key)
{
    dictEntry *he;
    unsigned int h, idx, table;

    if (d->ht[0].size == 0) return NULL; /* We don't have a table at all */
    if (dictIsRehashing(d)) _dictRehashStep(d);
    h = dictHashKey(d, key);
    for (table = 0; table <= 1; table++) {
        idx = h & d->ht[table].sizemask;
        he = d->ht[table].table[idx];
        while(he) {
            if (dictCompareKeys(d, key, he->key))
                return he;
            he = he->next;
        }
        if (!dictIsRehashing(d)) return NULL;
    }
    return NULL;
}

/* ZSETs use a specialized version of Skiplists */
typedef struct zskiplistNode {
    robj *obj;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned int span;
    } level[];
} zskiplistNode;

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;
    int level;
} zskiplist;

zskiplist *zslCreate(void);
void zslFree(zskiplist *zsl);
zskiplistNode *zslInsert(zskiplist *zsl, double score, robj *obj);
int zslDelete(zskiplist *zsl, double score, robj *obj);
zskiplistNode *zslFirstInRange(zskiplist *zsl, zrangespec *range);
zskiplistNode *zslLastInRange(zskiplist *zsl, zrangespec *range);
unsigned int zsetLength(robj *zobj);
void zsetConvert(robj *zobj, int encoding);
unsigned long zslGetRank(zskiplist *zsl, double score, robj *o);

typedef struct zset {
    dict *dict;
    zskiplist *zsl;
} zset;

#include <cstdio>
#include <cstring>

#include <iostream>
#include <string>

#include <sys/socket.h>
#include <netdb.h>

using namespace std;

string getnameinfo_str(const sockaddr *addr, socklen_t addrlen, int flags) {
    char host[NI_MAXHOST];
    char service[NI_MAXSERV];
    int ret = getnameinfo(addr, addrlen, host, sizeof(host), service, sizeof(service), flags);
    if (ret != 0) {
        fprintf(stderr, "getnameinfo failed, ret: %d, str: %s\n", ret, gai_strerror(ret));
    }
    return host + string(":") + service;
}

void work(const string &host, const string &service, int hints_flags, int getaddrinfo_flags) {
    printf("host: %s, service: %s, hints_flags: %d, getaddrinfo_flags: %d\n", host.c_str(), service.c_str(), hints_flags, getaddrinfo_flags);
    addrinfo hints;
    addrinfo *result;
    memset(&hints, 0, sizeof(hints));

    hints.ai_socktype = SOCK_STREAM;
    hints.ai_family = AF_UNSPEC;
    hints.ai_flags = hints_flags;

    int ret = getaddrinfo(host == "-" ? NULL : host.c_str(), service == "-" ? NULL : service.c_str(), &hints, &result);
    if (ret != 0) {
        fprintf(stderr, "getaddrinfo, host: %s, service: %s, ret: %d, str: %s\n", host.c_str(), service.c_str(), ret, gai_strerror(ret));
        return;
    }
    for (addrinfo *p = result; p != NULL; p = p->ai_next) {
        printf("addr: %s, flags: %d, family: %d, socktype: %d, procotol: %d\n",
               getnameinfo_str(p->ai_addr, p->ai_addrlen, getaddrinfo_flags).c_str(), p->ai_flags, p->ai_family, p->ai_socktype, p->ai_protocol);
        if (p == result && (hints_flags & AI_CANONNAME)) {
            printf("canonname: %s\n", p->ai_canonname);
        }
    }

    freeaddrinfo(result);

    puts("-----------");
}

int main(int argc, char **argv) {
    string host, service;
    int hints_flags, getaddrinfo_flags;
    while (cin >> host >> service >> hints_flags >> getaddrinfo_flags) {
        work(host, service, hints_flags, getaddrinfo_flags);
    }

    work("-", "https", AI_PASSIVE, 0);
    work("-", "https", 0, 0);
    work("-", "https", AI_PASSIVE | AI_CANONNAME, 0);

    work("127.0.0.1", "https", AI_PASSIVE, 0);
    work("127.0.0.1", "https", AI_PASSIVE | AI_CANONNAME, 0);
    work("127.0.0.1", "https", AI_PASSIVE | AI_CANONNAME, NI_NUMERICHOST | NI_NUMERICSERV);

    work("localhost", "http", AI_CANONNAME, 0);
    work("localhost", "http", AI_CANONNAME, NI_NUMERICHOST | NI_NUMERICSERV);

    work("baidu.com", "http", AI_CANONNAME, 0);
    work("baidu.com", "http", AI_CANONNAME, NI_NUMERICHOST | NI_NUMERICSERV);

    work("google.com", "http", AI_CANONNAME, 0);
    work("google.com", "http", AI_CANONNAME, NI_NUMERICHOST | NI_NUMERICSERV);

    return 0;
}