#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include typedef unsigned long long ull; #define mp make_pair #define pb push_back const long double eps = 1e-9; const double pi = acos(-1.0); const long long inf = 1e18; using namespace std; // ************************************************* int readInt(int l, int r, string name){ int x; if(scanf("%d", &x) != 1){ fprintf(stderr, "Expected int %s in range [%d, %d], but haven't found!", name.c_str(), l, r); throw; } if(!(l <= x && x <= r)){ fprintf(stderr, "Expected int %s in range [%d, %d], but found %d!", name.c_str(), l, r, x); throw; } return x; } // ************************************************* int fib[ 39 ]; set< int > taken; pair< int, string > reachable[ 200200 ]; int num = 0; void rec( int x, string s, int start ) { if ( taken.find( x ) != taken.end() ) return; taken.insert( x ); reachable[ ++num ] = make_pair( x, s ); string add = ""; for ( int i = 1; i < start; i++ ) add += "."; for ( int i = start; i < 39; i++ ) { if ( 1ll * x * fib[i] > 100000000 ) break; rec( x * fib[i], s + add + ".#.", i ); add += '.'; } } int fun( string s ) { int a = 0, b = 1; for ( int i = 1; i < s.size(); i++ ) { int c = ( s[i] == '#' ? 0 : a + b ); a = b; b = c; cout << c << " "; } return b; } void solve() { int l = readInt( 0, 100000000, "L" ); int r = readInt( l, 100000000, "R" ); int n = readInt( 1, 100000, "N" ); if ( l == 0 && n == 1 ) { puts("0 #"); return; } if ( l == 0 ) l++, n--; if ( reachable[ num ].first < l ) { puts("-1"); return; } int left_bound = num; { int left = 1, right = num - 1; while ( left <= right ) { int middle = ( left + right ) / 2; if ( l <= reachable[ middle ].first ) { left_bound = min( left_bound, middle ); right = middle - 1; } else left = middle + 1; } } int right_bound = 1; { int left = 2, right = num; while ( left <= right ) { int middle = ( left + right ) / 2; if ( reachable[ middle ].first <= r ) { right_bound = max( right_bound, middle ); left = middle + 1; } else right = middle - 1; } } if ( right_bound - left_bound + 1 < n ) { puts( "-1" ); return; } int index = left_bound + n - 1; printf("%d ", reachable[ index ].first ); for ( int i = 0; i < reachable[ index ].second.size(); i++ ) putchar( reachable[ index ].second[ i ] ); //cout << " " << fun( reachable[ index ].second ); putchar( '\n' ); } int main (int argc, const char * argv[]) { time_t start = clock(); fib[0] = fib[1] = 1; for ( int i = 2; i < 39; i++ ) fib[i] = fib[i - 1] + fib[i - 2]; rec( 1, ".", 2 ); sort( reachable + 1, reachable + num + 1 ); //for ( int i = 0; i < 20; i++ ) cout << reachable[i].first << " " << reachable[i].second << "\n"; int t = readInt( 1, 100000, "T" ); for ( int i = 0; i < t; i++ ) solve(); cerr << fixed << setprecision( 6 ) << "Time: " << 1.0 * ( clock() - start ) / CLOCKS_PER_SEC << "\n"; return 0; }