{"raw_statement":[{"iden":"problem statement","content":"This is an **interactive task**, where your and the judge's programs interact via Standard Input and Output.\nYou and the judge will follow the procedure below. The procedure consists of phases $1$ and $2$; phase $1$ is immediately followed by phase $2$.\n(Phase $1$)\n\n*   The judge gives you an integer $N$.\n*   You print an integer $M$ between $1$ and $50000$, inclusive.\n*   You also print $M$ pairs of integers $(l_1, r_1), (l_2, r_2), \\ldots, (l_M, r_M)$ such that $1 \\leq l_i \\leq r_i \\leq N$ for every $i = 1, 2, \\ldots, M$ (the $M$ pairs do not have to be distinct).\n\n(Phase $2$)\n\n*   The judge gives you an integer $Q$.\n*   You and the judge repeats the following $Q$ times.\n    *   The judge gives you two integers $L$ and $R$ as a query.\n    *   You respond with two integers $a$ and $b$ between $1$ and $M$, inclusive (possibly with $a = b$). Here, $a$ and $b$ must satisfy the condition below. Otherwise, your submission will be judged incorrect.\n        *   The union of the set $\\lbrace l_a, l_a+1, \\ldots, r_a\\rbrace$ and the set $\\lbrace l_b, l_b+1, \\ldots, r_b\\rbrace$ equals the set $\\lbrace L, L+1, \\ldots, R\\rbrace$.\n\nAfter the procedure above, terminate the program immediately to be judged correct."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 4000$\n*   $1 \\leq Q \\leq 10^5$\n*   $1 \\leq L \\leq R \\leq N$\n*   All values in the input are integers."},{"iden":"input and output","content":"This is an interactive task, where your and the judge's programs interact via Standard Input and Output.\n(Phase $1$)\n\n*   First, $N$ is given from the input.\n*   Next, an integer $M$ between $1$ and $50000$, inclusive, should be printed.\n*   Then, $(l_1, r_1), (l_2, r_2), \\ldots, (l_M, r_M)$ should be printed, one at a time. Specifically, for each $i = 1, 2, \\ldots, M$, the $i$\\-th output should be $(l_i, r_i)$ in the following format:\n\n$l_i$ $r_i$\n\n(Phase $2$)\n\n*   First, $Q$ is given from the input.\n*   In each query, integers $L$ and $R$ representing the query are given in the following format:\n\n$L$ $R$\n\n*   In response to each query, two integers $a$ and $b$ should be printed in the following format:\n\n$a$ $b$"},{"iden":"cautions","content":"*   **At the end of each output, print a newline and flush Standard Output. Otherwise, you may get the TLE verdict.**\n*   **If your program prints a malformed output or quits prematurely, the verdict will be indeterminate.** Particularly, note that in case of a runtime error, the verdict may be WA or TLE instead of RE.\n*   After phase $2$, immediately terminate the program. Otherwise, the verdict will be indeterminate.\n*   $L$ and $R$ given in phase $2$ will be decided according to $(l_1, r_1), (l_2, r_2), \\ldots, (l_M, r_M)$ you print in phase $1$."},{"iden":"sample interaction","content":"Below is a sample interaction with $N = 4$ and $Q = 4$.\n\nInput\n\nOutput\n\nDescription\n\n`4`\n\n$N$ is given.\n\n`6`\n\nYou print $M$.\n\n`3 3`\n\nYou print $(l_1, r_1) = (3, 3)$.\n\n`4 4`\n\nYou print $(l_2, r_2) = (4, 4)$.\n\n`1 1`\n\nYou print $(l_3, r_3) = (1, 1)$.\n\n`2 4`\n\nYou print $(l_4, r_4) = (2, 4)$.\n\n`1 3`\n\nYou print $(l_5, r_5) = (1, 3)$.\n\n`2 2`\n\nYou print $(l_6, r_6) = (2, 2)$.\n\n`4`\n\n$Q$ is given.\n\n`1 3`\n\nAs the first query, $L = 1$ and $R = 3$ are given.\n\n`1 5`\n\nYou respond with $a = 1$ and $b = 5$.\n\n`3 4`\n\nAs the second query, $L = 3$ and $R = 4$ are given.\n\n`2 1`\n\nYou respond with $a = 2$ and $b = 1$.\n\n`2 4`\n\nAs the third query, $L = 2$ and $R = 4$ are given.\n\n`4 4`\n\nYou respond with $a = 4$ and $b = 4$.\n\n`1 1`\n\nAs the fourth query, $L = 1$ and $R = 1$ are given.\n\n`3 3`\n\nYou respond with $a = 3$ and $b = 3$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}