Rules and Notes

• Rules and notes for this problem
  • In this problem, if a submitted solution receives any result other than CE, no further submissions to this problem will be accepted for the next $5$ minutes.
  • You can view the score rankings from the "Score Order" tab above or from the leaderboard.
  • Publishing discussions of or solutions to the problem during the contest is prohibited. This contest ends at 2022/10/15 01:20 (JST).
  • There is no visualizer.
  • No rejudging or system tests are planned after the contest ends.
  • Your score is the highest score among the solutions you submitted during the contest, and participants are ranked in descending order of score.
• Rules and notes for the contest
  • This problem is one of the problems in yukicoder contest 364 (Do you know Cherry Contest?). Be careful with how you allocate your time.
  • The points awarded for this problem are determined as follows.
    • No submission or a score of $0$ points $\cdots$ $0$ points.
    • A score of $1$ point or more $\cdots$ if your rank among the participants with a score of $1$ point or more is $R$, $\left(100+\left \lfloor 800 \exp \left(-\dfrac{R-1}{25} \right) \right \rfloor \right)$ points.

      Examples of ranks and their points

      Rank	1	2	3	4	5	10	15	20	25	30	35	40	45	50	60	70	80	90	100	125	150	200	$\cdots$
      Points	900	868	838	809	781	658	556	474	406	350	305	268	237	212	175	150	133	122	115	105	102	100	$\cdots$

Story

Consider a simple pendulum turned into a discrete model.

You are given several times. We would like you to build discrete pendulums so that, at these times, the weights of the discrete pendulums are as "split to the left and right" as possible in some states and as "gathered together" as possible in others.

However, please note that since air resistance has been incorporated into the model, the amplitude of each weight keeps decreasing as time passes.

Problem Statement

There are $N$ discrete pendulums (a term coined just for this problem) $P_1, \dots, P_N$, as illustrated in the figure below. Each $P_i$ consists of a coordinate axis and 1 piece.

For each $P_i$, you may freely set an initial amplitude $B_i$, a minimum amplitude $M_i$, and a damping amplitude $E_i$ within the range satisfying the following.

• $B_i, M_i, E_i$ are integers.
• $1 \leq M_i \leq B_i \leq 10^9$
• $1 \leq E_i \leq 10^9$

Each discrete pendulum $P_i$ moves as follows.

• At time $0$, the piece is at coordinate $0$.
• The amplitude $A_i$ at time $0$ is $A_i \gets B_i$. Also, let $D_i$ be an integer representing the direction, and set $D_i \gets 1$.
• At times $0.5, 1.5, 2.5, \dots, n-0.5~(n$ is a positive integer $), \dots$, the following occurs.
  • When the piece is at coordinate $x$, move the piece to coordinate $y:=(x+D_i)$.
  • If $y=D_iA_i$, do the following.
    • $D_i \gets -D_i$
    • $A_i \gets \max (M_i, A_i-E_i)$

These $N$ discrete pendulums will be photographed at times $T_1, \dots, T_K, U_1, \dots, U_K$. Your goal is to build discrete pendulums that achieve the following as well as possible.

• At times $T_1, \dots, T_K$, confrontation photos are taken. In these photos, we want the pieces to be split to the left and right as much as possible.
• At times $U_1, \dots, U_K$, cooperation photos are taken. In these photos, we want the pieces to be gathered at 1 location as much as possible.

Confrontation photos and cooperation photos are taken alternately (which comes first depends on the test case). Also, after a photo is taken at some time, the next photo is taken after waiting for at least $\Delta$.

The figure below is a table illustrating, as an example, the movement of a discrete pendulum with $B_i=10, M_i=3, E_i=2$.

Constraints

• $N$ is fixed at $50$.
• $K$ is fixed at $50$.
• $\Delta$ is fixed at $200$ (however, it is not given in the input).
• Exactly one of the following (Condition 1) and (Condition 2) holds.
  • (Condition 1)
    • $0 \leq T_1 \lt U_1 \lt T_2 \lt U_2 \lt \dots \lt T_K \lt U_K \leq 10^9$.
    • $T_i-U_{i-1} \geq \Delta \quad (i=1,2, \dots, K)$, where $U_0=0$.
    • $U_i-T_i \geq \Delta \quad (i=1,2, \dots, K)$.
  • (Condition 2)
    • $0 \leq U_1 \lt T_1 \lt U_2 \lt T_2 \lt \dots \lt U_K \lt T_K \leq 10^9$
    • $U_i-T_{i-1} \geq \Delta \quad (i=1,2, \dots, K)$, where $T_0=0$.
    • $T_i-U_i \geq \Delta \quad (i=1,2, \dots, K)$.

Scoring

For each of the $2K$ photos, the raw score $R$ of the photo is defined as follows, where $X_i$ is the coordinate of the $i$-th discrete pendulum shown in the photo.

• For a confrontation photo: $\displaystyle R:=\operatorname{round} \left(\dfrac{2 \times 10^7}{N(N-1)} \times \sum_{i=1}^{N-1} \sum_{k=i+1}^N \dfrac{\left|X_i-X_k \right|}{B_i+B_k} \right)$
• For a cooperation photo: $\displaystyle R:=\operatorname{round} \left(\dfrac{10^7}{\displaystyle \sqrt{\left ( \dfrac{1}{20}\max_{1 \leq i \lt k \leq N} \left|X_i-X_k \right| \right ) +1}} \right)$

Let $S_{{\rm confrontation}}$ be the average of the raw scores of the $K$ confrontation photos, and $S_{{\rm cooperation}}$ be the average of the raw scores of the $K$ cooperation photos (both rounded to the nearest integer). The score for the test case is the product $S_{{\rm confrontation}} \times S_{{\rm cooperation}}$.

There are $50$ test cases in total, and the score of a submission is the sum of the scores over all test cases. However, if the verdict is anything other than AC on $1$ or more test cases, the score of the submission is $0$ points regardless of the results on the other test cases. The final ranking is determined by the highest score obtained during the contest, and no system tests are performed after the contest ends. If multiple participants obtain the same score, the one whose submission achieving that score was made earlier is ranked higher.

Input

The input is given from Standard Input in the following format.

$N$ $K$
$T_1$ $T_2$ $\cdots$ $T_K$
$U_1$ $U_2$ $\cdots$ $U_K$

Output

The output consists of $N$ lines.

On the $i$-th line $(1 \leq i \leq N)$, output the initial amplitude $B_i$, the minimum amplitude $M_i$, and the damping amplitude $E_i$ of the $i$-th discrete pendulum in this order, separated by spaces.

Do not forget the newline after the $N$-th line as well.

$B_1$ $M_1$ $E_1$
$B_2$ $M_2$ $E_2$
$\vdots$
$B_N$ $M_N$ $E_N$

If you output more than $N$ lines, only the first $N$ lines are used for judging.

The judge result for output that does not follow this format is undefined (it is not necessarily WA or RE).

Input Generation

Let $\operatorname{rand}()$ be a function that uniformly randomly generates a double-precision floating-point number that is at least $0$ and less than $1$.

Also, when creating each test case, a test case number ${\rm id}$ (at least $1$ and at most $50$ (added 2022/10/14 23:30)) is given at generation time.

Generation of $N, K, \Delta$

Let $N \gets 50, K \gets 50, \Delta \gets 200$.

Generation of $T_j, U_j$

Set $2K$ real numbers $F_1, F_2, \dots, F_{2K}$ as $F_j \gets \operatorname{rand}()~(j=1,2, \dots, 2K)$. However, for any $j$ with $F_j=0$, regenerate $F_j$ for such $j$. Then, set $G_0, \dots, G_{2K}$ as follows.

• $G_0=0$
• $G_j=\operatorname{round} \left(G_{j-1}+\dfrac{\Delta}{F_j} \right)$

• If ${\rm id}$ is odd, $T_j \gets G_{2j-1}, U_j \gets G_{2j}$.
• If ${\rm id}$ is even, $T_j \gets G_{2j}, U_j \gets G_{2j-1}$.

Examples

50 50
643 2273 2952 4329 4922 7885 50581 52055 64796 65770 66449 68315 69508 70381 72692 73163 73729 81456 82537 83376 85326 86242 87664 88896 89494 90464 91043 92064 94327 99677 100710 101619 102734 103385 104377 105917 107307 107715 109032 109955 112314 112952 113540 114330 115094 121702 125533 126606 127354 128119
213 947 2499 4015 4564 5217 8137 51427 61121 65495 66213 66938 69269 70000 70597 72949 73444 75618 82172 82764 85099 85993 87137 88675 89115 89819 90683 91695 92337 96181 99895 101241 102008 103166 103609 104938 107097 107515 108155 109456 110935 112571 113152 113922 114541 115365 125327 125826 127137 127698

836 746 22
460 421 10
487 346 113
396 256 74
846 622 96
730 314 15
971 703 56
838 449 307
583 215 320
420 197 114
535 110 137
682 589 13
597 172 61
992 830 95
629 206 10
459 395 33
869 251 599
528 479 12
684 138 196
159 156 0
763 445 200
922 776 19
679 567 4
588 460 107
884 663 197
505 475 6
488 113 187
800 617 7
553 104 110
961 626 331
617 522 75
969 250 110
982 377 331
873 658 109
820 431 377
902 778 98
664 606 33
271 165 27
788 163 272
762 438 65
458 375 31
360 148 52
375 309 56
635 554 73
510 349 63
285 152 129
660 615 45
995 380 585
853 798 24
921 601 205