Input and Output

This problem is interactive. Read the following explanation, and communicate with the judge program accordingly.

At first, problem parameters and the initial state will be provided from Standard Input in the following format.

\(
N ~ M ~ K ~ T \\
t_0 ~ w_0 \\
\vdots \\
t_{N-1} ~ w_{N-1} \\
h_0 ~ v_0 \\
\vdots \\
h_{M-1} ~ v_{M-1} \)

• On the first line, there are four integers N,M,K,T separated by spaces.
• N represents the number of policy cards in your hand and satisfies 2 \le N \le 7.
• M represents the number of projects managed by the company and satisfies 2 \le M \le 8.
• K represents the number of policy card candidates presented for refilling the hand and satisfies 2 \le K \le 5.
• T represents the number of turns and satisfies T = 1000.
• The following N lines provide information about the policy cards in the starting hand.
• Each line contains space-separated two integers t_i and w_i, representing the type and labor power of the i-th policy card.
• When t_i = 0, it indicates that the card is a Regular Work card with labor power w_i.
• When t_i = 1, it indicates that the card is a Hard Work card with labor power w_i.
• When t_i = 2, it indicates that the card is a Cancel card.
• When t_i = 3, it indicates that the card is a Restructuring card.
• When t_i = 4, it indicates that the card is an Investment card.
• The ranges of values for t_i, w_i (0 \leq i \lt N) are described in the "Input Generation" section.
• The following M lines provide information about the projects at the start of the game.
• Each line contains space-separated two integers h_i and v_i, representing the remaining work and value of the i-th project.
• The ranges of values for h_i, v_i (0 \leq i \lt M) are described in the "Input Generation" section.

After receiving the above input, the game will progress over T turns. Communicate with the judge program in the following format each turn.

First, choose one policy card to use from your hand, and output the information of that card to the Standard Output in the following format.

\(
c ~ m\)

• On a single line, output two integers c,m separated by a space.
• c represents the position of the policy card to be used from the hand.
• m represents the position of the project on which to apply the effect of the card.
• 0 \leq c \lt N, 0 \leq m \lt M must be satisfied.
• If the chosen card is a Hard Work card, Restructuring card, or Investment card, m must be 0.
• Investment card can only be used up to 20 times within a single test case.
• If the output does not satisfy the constraints, the result will be WA.
• The output must be followed by a new line, and you have to flush Standard Output. Otherwise, the submission might be judged as TLE
  

Next, receive the information about the status of the projects after using the card from the Standard Input.

\(          
h_0 ~ v_0 \\
\vdots \\
h_{M-1} ~ v_{M-1} \)

• The input consists of M lines, with each line providing the information about the projects immediately after using the previous policy card, in the same format as the initial input.
• If there are completed or aborted projects, the information about the newly generated projects will be provided at the same position as those projects.

Next, receive the information about the current money from the Standard Input.

\(
money\)

• A single integer money is provided, representing the current money at this point.

Next, receive the information about the candidate policy cards to refill the hand from the Standard Input.

\(
t_0 ~ w_0 ~ p_0 \\
\vdots \\
t_{K-1} ~ w_{K-1} ~ p_{K-1} \)

• The input consists of K lines, each containing three integers separated by spaces
• t_i, w_i represent the information of the i-th candidate policy card in the same format as the initial input.
• p_i represents the cost of the i-th policy card.
• t_0, w_0, p_0 satisfy t_0 = 0, w_0 = 2^L, p_0 = 0. Here, let L ( 0 \leq L \leq 20 ) be an integer representing the number of times the Investment card has been used at this point.
• The ranges of values for t_i, w_i, p_i (1 \leq i \lt K) are described in the "Input Generation" section.

Finally, output to the standard output the information about which of the K candidate policy cards to add to the hand.

\(
r\)

• On a single line, output an integer r.
• This indicates selecting the r-th policy card from the candidate policy cards.
• 0 \le r \lt K must be satisfied.
• You cannot choose a card that would result in a negative money.
• The card chosen here will refill the hand in the same position as the card used at the beginning of this turn, which is the c-th position in the hand.
• If the output does not satisfy the constraints, the result will be WA.
• The output must be followed by a new line, and you have to flush Standard Output. Otherwise, the submission might be judged as TLE
  

This concludes one turn.

Input Generation

• For integers l and r satisfying l \leq r, let \mathrm{rand}(l, r) be a function that generates a uniformly random integer between l and r, inclusive.
• For real numbers l and r satisfying l \leq r, let \mathrm{rand\_double}(l, r) be a function that generates a uniformly random real number between l and r, inclusive.
• Let \mathrm{gauss}(μ, σ) be a function that generates values from a normal distribution with mean μ and standard deviation σ.
• For real numbers l and r satisfying l \leq r, and a real number x, let \mathrm{clamp}(x, l, r) be a function that calculates \mathrm{max}(l, \mathrm{min}(r, x)) .

Generation of N, M, K

• N = \mathrm{rand}(2, 7)
• M = \mathrm{rand}(2, 8)
• K = \mathrm{rand}(2, 5)

Generation of projects

• Let L ( 0 \leq L \leq 20 ) be an integer representing the number of times the Investment card has been used at this point.
• Generate a parameter b = \mathrm{rand\_double}(2.0, 8.0).
• Remaining work h is generated as h = \mathrm{round}(2 ^ b) * 2^L.
• Value v is generated as v = \mathrm{round}(2 ^ {\mathrm{clamp}(\mathrm{gauss}(b, 0.5), 0.0, 10.0)}) * 2^L.

Generation of policy cards

• For each test case, the hidden parameters x_0, x_1, x_2, x_3, x_4 are defined to control the generation probabilities of the card types as follows:
• x_0=\mathrm{rand}(1,20), x_1=\mathrm{rand}(1,10), x_2=\mathrm{rand}(1,10), x_3=\mathrm{rand}(1,5), x_4=\mathrm{rand}(1,3)
• The probability of the card type t being i is proportional to x_i (0 \leq i \leq 4).
• Let L ( 0 \leq L \leq 20 ) be an integer representing the number of times the Investment card has been used at this point.
• If t=0 or t = 1, labor power w is generated as w=\mathrm{rand}(1, 50)* 2^L. For t other than 0,1, w is set to 0.
• The cost p of the policy card is determined as follows:
• When t = 0, let w' = w/2^L and p is generated as p = \mathrm{clamp}(\mathrm{round}(\mathrm{gauss}(w', w'/3)), 1, 10000) * 2^L .
• When t = 1, let w' = w/2^L and p is generated as p = \mathrm{clamp}(\mathrm{round}(\mathrm{gauss}(w'*M, w'*M/3)), 1, 10000) * 2^L .
• When t = 2, p is generated as p = \mathrm{rand}(0, 10) * 2^L .
• When t = 3, p is generated as p = \mathrm{rand}(0, 10) * 2^L .
• When t = 4, p is generated as p = \mathrm{rand}(200, 1000) * 2^L .

Tools (Input generator, local tester and visualizer)

• Web version: For displaying animated visualizations.
• Local version: You need a compilation environment of Rust language.
  • Pre-compiled binary for Windows: If you are not familiar with the Rust language environment, please use this instead.
• Sample code (C++, Python): Sample answers. Implemented as follows:
  • When using a policy card, always use the 0-th card. If the card is a Regular Work card or a Cancel card, it targets the 0-th project.
  • When selecting which policy card to add to the hand from the candidate policy cards, always choose the 0-th policy card.
    • The cost of the 0-th candidate policy card is guaranteed to be 0, making this choice always possible regardless of the current money.

Please be aware that sharing visualization results or discussing solutions/ideas during the contest is prohibited.

Specification of input/output files used by the tools

Input files given to the local tester have the following format.

\(
N ~ M ~ K ~ T \\
h_{init,0} ~ v_{init,0} \\
\vdots \\
h_{init,M-1} ~ v_{init,M-1} \\
h_{0} ~ v_{0} \\
\vdots \\
h_{T*M-1} ~ v_{T*M-1} \\
t_{init,0} ~ w_{init,0} \\
\vdots \\
t_{init,N-1} ~ w_{init,N-1} \\
t_{0,0} ~ w_{0,0} ~ p_{0,0} \\
\vdots \\
t_{0,K-1} ~ w_{0,K-1} ~ p_{0,K-1} \\
t_{1,0} ~ w_{1,0} ~ p_{1,0} \\
\vdots \\
t_{T-1,K-1} ~ w_{T-1,K-1} ~ p_{T-1,K-1} \)

• h_{init,i}, v_{init,i} represent the remaining work and value of the i-th project given at the beginning.
• h_{i}, v_{i} represent the remaining work and value of the newly generated projects, and they are used sequentially from the beginning. When generating new projects, these values are multiplied by 2^L, where L is the number of times the Investment card has been used.
• t_{init,i}, w_{init,i} represent the type and labor power of the i-th policy card given at the beginning
• t_{i,j}, w_{i,j}, p_{i,j} represent the type, labor power, and cost of the j-th candidate policy card given in the i-th turn. When generating new policy card, these values are multiplied by 2^L, where L is the number of times the Investment card has been used.

The local tester writes outputs from your program directly to the output file. Your program may output comment lines starting with #. The web version of the visualizer displays the comment lines with the corresponding turn, which may be useful for debugging and analysis. Since the judge program ignores all comment lines, you can submit a program that outputs comment lines as is.