//By anudeep #include #include #include #include #include #include using namespace std; #define N 100000000 #define mp make_pair #define M 111111 #define rep(i, n) for(int i=0; i, int> parent; bool cmp(int i, int j) { return L[i] < L[j]; } // This function is used for printing the path. // We recorded the parent node when we did bfs. We travel back from answer to 0. void print(int n) { if(n == -1) { printf("\n"); return; } int a = n, b = 0; int ptr = 0; while(a != -1) { if(b==0) ans[ptr++] = '#'; else ans[ptr++] = '.'; int c = parent[ mp(a,b) ]; b = a; a = c; } for(int i=0; i q; // We start with the state (0, 1) q.push(0); q.push(1); parent[ mp(0,1) ] = -1; // We do a bfs to visit all possible states while(!q.empty()) { int a = q.front(); q.pop(); int b = q.front(); q.pop(); if(b == 0) valid[validPtr++] = a; // This is a valid candidate, it is of the form (x, 0) int c,d; c = b; d = a+b; for(int i=0; i<2; i++) { if(d <= N && parent.find(mp(c,d)) == parent.end()) { parent[mp(c,d)] = a; q.push(c); q.push(d); } c = b; d = 0; } } // Sort all possible answers sort(valid, valid+validPtr); int m; scanf("%d", &m); rep(i, m) { scanf("%d%d%d", &L[i], &R[i], &nth[i]); order[i] = i; } // Sorting the queries, can be done online with binary search as well sort(order, order+m, cmp); int ptr = 0; rep(mm, m) { int j = order[mm]; while(ptr < validPtr && valid[ptr] < L[j]) ptr++; int n = ptr + nth[j] - 1; if(n < validPtr) { n = valid[n]; } else { n = N + 100; } if(n > R[j]) { numAns[j] = -1; continue; } numAns[j] = n; } rep(i, m) { printf("%d ", numAns[i]); print(numAns[i]); } }