/*
//BAEKJOON 1697_숨바꼭질(완)
#include <stdio.h>
#include <queue>
#include <vector>

using namespace std;

vector<int> G[100010];
int n, k, depth[100010], flag=0;

int main() {

    scanf("%d %d", &n, &k);

    for(int i=0; i<100001; i++) {
        if(i>0) G[i].push_back(i-1);
        if(i<100000) G[i].push_back(i+1);
        if(i<=50000) G[i].push_back(2*i);

        depth[i]=-1;
    }

    queue<int> q;
    q.push(n);
    depth[n]=0;

    while(!q.empty()) {
        int v=q.front();
        q.pop();

        for(int i=0; i<G[v].size(); i++) {
            if(depth[G[v][i]]==-1) {
                q.push(G[v][i]);
                depth[G[v][i]]=depth[v]+1;
                if(G[v][i]==k) {
                    flag=1; break;
                }
            }
        }

        if(flag) break;
    }
    printf("%d", depth[k]);
}

//BAEKJOON 14940_쉬운 최단경로(완)
#include <stdio.h>
#include <queue>

using namespace std;

struct node {
    int x;
    int y;
};

int n, m, G[1010][1010], depth[1010][1010], dx[4]={1, 0, -1, 0}, dy[4]={0, -1, 0, 1};

void bfs(int x, int y) {
    queue<node> q;
    q.push({x, y});
    depth[x][y]=0;

    while(!q.empty()) {
        node v=q.front();
        q.pop();
        int X=v.x, Y=v.y;

        for(int i=0; i<4; i++) {
            int nx=X+dx[i], ny=Y+dy[i];

            if(G[nx][ny]==1 && depth[nx][ny]==-1) {
                q.push({nx, ny});
                depth[nx][ny]=depth[X][Y]+1;
            }
        }
    }
}

int main() {
    int x, y;

    scanf("%d %d", &n, &m);

    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            scanf("%d", &G[i][j]);
            if(G[i][j]==2) {
                x=i; y=j;
            }
        }
    }

    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            depth[i][j]=-1;
        }
    }
    
    bfs(x, y);
    
    for(int i=1; i<=n; i++, puts("")) {
        for(int j=1; j<=m; j++) {
            if(depth[i][j]==-1) {
                if(G[i][j]==0) printf("0 ");
                else printf("-1 ");
            }
            else printf("%d ", depth[i][j]);
        }
    }
}

//BAEKJOON 17219_비밀번호 찾기(완) : 이분탐색
#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;

struct pw {
    char site[25];
    char PW[25];
};

int n, m;
pw S[100000];

bool cmp(pw a, pw b) {
    return strcmp(a.site, b.site) < 0;
}

int binary_search(char s[25]) {
    int low=0, high=n-1;

    while(low<=high) {
        int mid=(low+high)/2;
        if(strcmp(s, S[mid].site) > 0) low=mid+1;
        else if(strcmp(s, S[mid].site) < 0) high=mid-1;
        else return mid;
    }
    return -1;
}

int main() {
    
    scanf("%d %d", &n, &m);

    for(int i=0; i<n; i++) {
        scanf("%s %s", S[i].site, S[i].PW);
    }

    sort(S, S+n, cmp);
    
    for(int i=0; i<m; i++) {
        char s[25];
        scanf("%s", s);

        printf("%s\n", S[binary_search(s)].PW);
    }
}

//BAEKJOON 11723_집합(완)
#include <stdio.h>
#include <string.h>

int arr[30];

int main() {
    int m;
    scanf("%d", &m);

    for(int i=0; i<m; i++) {
        char s[20];
        int x;
        scanf("%s", s);

        if(strcmp(s, "all")==0) {
            for(int i=1; i<21; i++) arr[i]=1;
        }
        else if(strcmp(s,"empty")==0) {
            for(int i=1; i<21; i++) arr[i]=0;
        }
        else {
            scanf("%d", &x);
            if(strcmp(s, "add")==0) arr[x]=1;
            else if(strcmp(s, "remove")==0) arr[x]=0;
            else if(strcmp(s, "check")==0) printf("%d\n", arr[x]);
            else if(strcmp(s, "toggle")==0) arr[x]=1-arr[x];
        }
    }
}

//BAEKJOON 2667_단지 번호 붙이기(완)
#include <stdio.h>
#include <algorithm>

int n, G[30][30], visited[30][30], dx[4]={1, 0, -1, 0}, dy[4]={0, -1, 0, 1}, cnt, cnt_tmp, CNT[626];

void dfs(int x, int y) {
    cnt_tmp++;
    visited[x][y]=1;

    for(int i=0; i<4; i++) {
        int nx=x+dx[i], ny=y+dy[i];
        if(G[nx][ny] && !visited[nx][ny]) dfs(nx, ny);
    }
}

int main() {

    scanf("%d", &n);

    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            scanf("%1d", &G[i][j]);

    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            if(G[i][j] && !visited[i][j]) {
                cnt_tmp=0;
                dfs(i, j);
                CNT[cnt++] = cnt_tmp;
            }
        }
    }

    std::sort(CNT, CNT+cnt);

    printf("%d\n", cnt);
    for(int i=0; i<cnt; i++)
        printf("%d\n", CNT[i]); 
    
}

//BAEKJOON 1764_듣보잡(완)
#include <stdio.h>
#include <string.h>
#include <algorithm>

struct str {
    char s[25];
};

int n, m, arr[500010], cnt;
str s1[500010], s2[500010];

bool cmp(str a, str b) {
    return strcmp(a.s, b.s) < 0;
}

int binary_search(char s[25]) { //사전순 정
    int low=0, high=n-1;

    while(low<=high) {
        int mid=(low+high)/2;
        if(strcmp(s, s1[mid].s) > 0) low=mid+1;
        else if(strcmp(s, s1[mid].s) < 0) high=mid-1;
        else return mid;
    }
    return -1;
}


int main() {

    scanf("%d %d", &n, &m);

    for(int i=0; i<n; i++) {
        scanf("%s", s1[i].s);
    }
    for(int i=0; i<m; i++) {
        scanf("%s", s2[i].s);
    }

    std::sort(s1, s1+n, cmp);
    
    for(int i=0; i<m; i++) {
        if(binary_search(s2[i].s)!=-1) {
            arr[cnt++]=binary_search(s2[i].s);
        }
    }

    std::sort(arr, arr+cnt);

    printf("%d\n", cnt);
    for(int i=0; i<cnt; i++) {
        printf("%s\n", s1[arr[i]].s);
    }
}

//BAEKJOON 11726_2xn 타일링(완)
#include <stdio.h>

int d0[1010], d1[1010]; //d0 : 1x2, d1 : 2x1

void f() {

    d0[1]=0; d1[1]=1;
    d0[2]=1; d1[2]=1;

    for(int i=3; i<1001; i++) {
        d0[i] = d0[i-2] + d1[i-2];
        d1[i] = d0[i-1] + d1[i-1];
        d0[i] %= 10007;
        d1[i] %= 10007;
    }
}

int main() {
    
    int n;
    scanf("%d", &n);

    f();

    printf("%d",(d0[n]+d1[n])%10007);
}

//BAEKJOON 11727_2xn 타일링2(완)
#include <stdio.h>

int d0[1010], d1[1010], d2[1010]; //d0 : 1x2, d1 : 2x1, d2 : 2x2

void f() {

    d0[1]=0; d1[1]=1; d2[1]=0;
    d0[2]=1; d1[2]=1; d2[2]=1;

    for(int i=3; i<1001; i++) {
        d0[i] = d0[i-2] + d1[i-2] + d2[i-2];
        d1[i] = d0[i-1] + d1[i-1] + d2[i-1];
        d2[i] = d0[i-2] + d1[i-2] + d2[i-2];
        d0[i] %= 10007;
        d1[i] %= 10007;
        d2[i] %= 10007;
        
    }
}

int main() {
    
    int n;
    scanf("%d", &n);

    f();

    printf("%d",(d0[n]+d1[n]+d2[n])%10007);
}
*/