DMOPC '19 Contest 1 P2 - Good Writing

View as PDF

Submit solution


Points: 7
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type

A teacher once said: "Good writing is good writing is good writing."
Hence, the teacher defines f_0 = "Good writing is good writing is good writing."
To make the quote more interesting the teacher defines f_n = "Good writing is good " +f_{n-1}+ " writing is good " + f_{n-1} + " is good writing." for all n \ge 1

For example, f_1 is

Good writing is good Good writing is good writing is good writing. writing is good Good writing is good writing is good writing. is good writing.

Note that the quotation marks are not part of f_1.

The teacher wants to ask q questions. Each time she wants to find the k-th character of f_n.
Characters are indexed starting at 1. If f_n consists of less than k characters, output .

Constraints

In all tests,
1 \le q \le 10
0 \le n \le 30
1 \le k \le 2^{31}-1

Input Specification

The first line contains an integer, q.
The following q lines each contains two integers, n and k in that order.

Output Specification

On the ith line, output the answer to the ith question.

Sample Input 1

3
0 4
1 100
1 1111111

Sample Output 1

d
g
.

Sample Input 2

3
0 6  
1 13
1 22

Sample Output 2

w

G

Comments

There are no comments at the moment.