atcoder#ABC282F. [ABC282F] Union of Two Sets

[ABC282F] Union of Two Sets

Score : 500500 points

Problem Statement

This is an interactive task, where your and the judge's programs interact via Standard Input and Output.

You and the judge will follow the procedure below. The procedure consists of phases 11 and 22; phase 11 is immediately followed by phase 22.

(Phase 11)

  • The judge gives you an integer NN.
  • You print an integer MM between 11 and 5000050000, inclusive.
  • You also print MM pairs of integers (l1,r1),(l2,r2),,(lM,rM)(l_1, r_1), (l_2, r_2), \ldots, (l_M, r_M) such that 1liriN1 \leq l_i \leq r_i \leq N for every i=1,2,,Mi = 1, 2, \ldots, M (the MM pairs do not have to be distinct).

(Phase 22)

  • The judge gives you an integer QQ.
  • You and the judge repeats the following QQ times.- The judge gives you two integers LL and RR as a query.
    • You respond with two integers aa and bb between 11 and MM, inclusive (possibly with a=ba = b). Here, aa and bb must satisfy the condition below. Otherwise, your submission will be judged incorrect.- The union of the set {la,la+1,,ra}\lbrace l_a, l_a+1, \ldots, r_a\rbrace and the set {lb,lb+1,,rb}\lbrace l_b, l_b+1, \ldots, r_b\rbrace equals the set {L,L+1,,R}\lbrace L, L+1, \ldots, R\rbrace.
  • The judge gives you two integers LL and RR as a query.
  • You respond with two integers aa and bb between 11 and MM, inclusive (possibly with a=ba = b). Here, aa and bb must satisfy the condition below. Otherwise, your submission will be judged incorrect.
  • The union of the set {la,la+1,,ra}\lbrace l_a, l_a+1, \ldots, r_a\rbrace and the set {lb,lb+1,,rb}\lbrace l_b, l_b+1, \ldots, r_b\rbrace equals the set {L,L+1,,R}\lbrace L, L+1, \ldots, R\rbrace.

After the procedure above, terminate the program immediately to be judged correct.

Constraints

  • 1N40001 \leq N \leq 4000
  • 1Q1051 \leq Q \leq 10^5
  • 1LRN1 \leq L \leq R \leq N
  • All values in the input are integers.

Input and Output

This is an interactive task, where your and the judge's programs interact via Standard Input and Output.

(Phase 11)

  • First, NN is given from the input.
  • Next, an integer MM between 11 and 5000050000, inclusive, should be printed.
  • Then, (l1,r1),(l2,r2),,(lM,rM)(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,,Mi = 1, 2, \ldots, M, the ii-th output should be (li,ri)(l_i, r_i) in the following format:
l_i r_i

(Phase 22)

  • First, QQ is given from the input.
  • In each query, integers LL and RR representing the query are given in the following format:
L R
  • In response to each query, two integers aa and bb should be printed in the following format:
a b

Cautions

  • At the end of each output, print a newline and flush Standard Output. Otherwise, you may get the TLE verdict.
  • 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.
  • After phase 22, immediately terminate the program. Otherwise, the verdict will be indeterminate.
  • LL and RR given in phase 22 will be decided according to (l1,r1),(l2,r2),,(lM,rM)(l_1, r_1), (l_2, r_2), \ldots, (l_M, r_M) you print in phase 11.

Sample Interaction

Below is a sample interaction with N=4N = 4 and Q=4Q = 4.

Input Output Description
4 NN is given.
6 You print MM.
3 3 You print (l1,r1)=(3,3)(l_1, r_1) = (3, 3).
4 4 You print (l2,r2)=(4,4)(l_2, r_2) = (4, 4).
1 1 You print (l3,r3)=(1,1)(l_3, r_3) = (1, 1).
2 4 You print (l4,r4)=(2,4)(l_4, r_4) = (2, 4).
1 3 You print (l5,r5)=(1,3)(l_5, r_5) = (1, 3).
2 2 You print (l6,r6)=(2,2)(l_6, r_6) = (2, 2).
4 QQ is given.
1 3 As the first query, L=1L = 1 and R=3R = 3 are given.
1 5 You respond with a=1a = 1 and b=5b = 5.
3 4 As the second query, L=3L = 3 and R=4R = 4 are given.
2 1 You respond with a=2a = 2 and b=1b = 1.
2 4 As the third query, L=2L = 2 and R=4R = 4 are given.
4 4 You respond with a=4a = 4 and b=4b = 4.
1 1 As the fourth query, L=1L = 1 and R=1R = 1 are given.
3 3 You respond with a=3a = 3 and b=3b = 3.