A. Nephren gives a riddle

Codeforces

IDCF896A

Time2000ms

Memory256MB

Difficulty—

binary searchdfs and similar

English · Original

Chinese · Translation

Formal · Original

> > _What are you doing at the end of the world? Are you busy? Will you save us?_<center>![image](https://espresso.codeforces.com/198e224c6a6e621ba2dd03f3d2926dc004894f99.png) </center>Nephren is playing a game with little leprechauns. She gives them an infinite array of strings, _f_0... ∞. _f_0 is "_What are you doing at the end of the world? Are you busy? Will you save us?_". She wants to let more people know about it, so she defines _f__i_ = "_What are you doing while sending "__f__i_ - 1_"? Are you busy? Will you send "__f__i_ - 1_"?_" for all _i_ ≥ 1. For example, _f_1 is "_What are you doing while sending "What are you doing at the end of the world? Are you busy? Will you save us?"? Are you busy? Will you send "What are you doing at the end of the world? Are you busy? Will you save us?"?_". Note that the quotes in the very beginning and in the very end are for clarity and are not a part of _f_1. It can be seen that the characters in _f__i_ are letters, question marks, (possibly) quotation marks and spaces. Nephren will ask the little leprechauns _q_ times. Each time she will let them find the _k_\-th character of _f__n_. The characters are indexed starting from 1. If _f__n_ consists of less than _k_ characters, output '_._' (without quotes). Can you answer her queries? ## Input The first line contains one integer _q_ (1 ≤ _q_ ≤ 10) — the number of Nephren's questions. Each of the next _q_ lines describes Nephren's question and contains two integers _n_ and _k_ (0 ≤ _n_ ≤ 105, 1 ≤ _k_ ≤ 1018). ## Output One line containing _q_ characters. The _i_\-th character in it should be the answer for the _i_\-th query. [samples] ## Note For the first two examples, refer to _f_0 and _f_1 given in the legend.

Nephren 正在和一些小精灵玩游戏。她给了他们一个无限长的字符串数组，#cf_span[f0... ∞]。 #cf_span[f0] 是 "_What are you doing at the end of the world? Are you busy? Will you save us?_"。她希望让更多人知道这个，于是她定义了对于所有 #cf_span[i ≥ 1]，#cf_span[fi = ] "_What are you doing while sending "_#cf_span[fi - 1]_"? Are you busy? Will you send "_#cf_span[fi - 1]_"?_"。例如，#cf_span[f1] 是 "_What are you doing while sending "What are you doing at the end of the world? Are you busy? Will you save us?"? Are you busy? Will you send "What are you doing at the end of the world? Are you busy? Will you save us?"?_"。注意，开头和末尾的引号仅为清晰起见，并不属于 #cf_span[f1] 的一部分。可以观察到，#cf_span[fi] 中的字符包括字母、问号、（可能的）引号和空格。 Nephren 将向小精灵们提问 #cf_span[q] 次。每次她会让他们找出 #cf_span[fn] 的第 #cf_span[k] 个字符。字符的索引从 #cf_span[1] 开始。如果 #cf_span[fn] 的字符数少于 #cf_span[k]，则输出 '_._'（不含引号）。你能回答她的提问吗？第一行包含一个整数 #cf_span[q] (#cf_span[1 ≤ q ≤ 10]) —— Nephren 的提问次数。接下来的 #cf_span[q] 行每行描述一个提问，包含两个整数 #cf_span[n] 和 #cf_span[k] (#cf_span[0 ≤ n ≤ 105, 1 ≤ k ≤ 1018])。输出一行包含 #cf_span[q] 个字符。第 #cf_span[i] 个字符应为第 #cf_span[i] 个查询的答案。对于前两个示例，请参考题面中给出的 #cf_span[f0] 和 #cf_span[f1]。 ## Input 第一行包含一个整数 #cf_span[q] (#cf_span[1 ≤ q ≤ 10]) —— Nephren 的提问次数。接下来的 #cf_span[q] 行每行描述一个提问，包含两个整数 #cf_span[n] 和 #cf_span[k] (#cf_span[0 ≤ n ≤ 105, 1 ≤ k ≤ 1018])。 ## Output 输出一行包含 #cf_span[q] 个字符。第 #cf_span[i] 个字符应为第 #cf_span[i] 个查询的答案。 [samples] ## Note 对于前两个示例，请参考题面中给出的 #cf_span[f0] 和 #cf_span[f1]。

**Definitions** Let $ f_0 = $ "_What are you doing at the end of the world? Are you busy? Will you save us?_" For $ i \geq 1 $, define: $$ f_i = \text{"What are you doing while sending \""} + f_{i-1} + \text{"\"? Are you busy? Will you send \""} + f_{i-1} + \text{"\"?"} $$ Let $ \ell_i = |f_i| $ denote the length of string $ f_i $. **Constraints** 1. $ 1 \leq q \leq 10 $ 2. For each query: $ 0 \leq n \leq 10^5 $, $ 1 \leq k \leq 10^{18} $ 3. $ \ell_0 = 67 $ 4. For $ i \geq 1 $: $$ \ell_i = 60 + 2 \cdot \ell_{i-1} $$ (since the fixed parts total 60 characters: "What are you doing while sending \"\"? Are you busy? Will you send \"\"?" minus the two embedded strings) **Objective** For each query $ (n, k) $: - If $ k > \ell_n $, output '.' - Else, output the $ k $-th character of $ f_n $ **Note**: $ \ell_i $ grows exponentially; for $ i \gtrapprox 60 $, $ \ell_i > 10^{18} $, so we may cap recursion at $ i \approx 60 $.

Samples

Input #1

3
1 1
1 2
1 111111111111

Output #1

Wh.

Input #2

Output #2

abdef

Input #3

Output #3

Areyoubusy

API Response (JSON)

{
  "problem": {
    "name": "A. Nephren gives a riddle",
    "description": {
      "content": "> > _What are you doing at the end of the world? Are you busy? Will you save us?_<center>![image](https://espresso.codeforces.com/198e224c6a6e621ba2dd03f3d2926dc004894f99.png) </center>Nephren is pla",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF896A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "> > _What are you doing at the end of the world? Are you busy? Will you save us?_<center>![image](https://espresso.codeforces.com/198e224c6a6e621ba2dd03f3d2926dc004894f99.png)\n\n</center>Nephren is pla...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Nephren 正在和一些小精灵玩游戏。\n\n她给了他们一个无限长的字符串数组，#cf_span[f0... ∞]。\n\n#cf_span[f0] 是 \"_What are you doing at the end of the world? Are you busy? Will you save us?_\"。\n\n她希望让更多人知道这个，于是她定义了对于所有 #cf_span[i ≥ 1]，#cf_s...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ f_0 = $ \"_What are you doing at the end of the world? Are you busy? Will you save us?_\"  \nFor $ i \\geq 1 $, define:  \n$$\nf_i = \\text{\"What are you doing while sending \\\"\"} + f_...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments