ICPC Thailand National Contest 2025 (Partial)
D. Do You Want to Build a Christmas Tree?
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Of course, you do.

Don't even try to resist it—you can already feel it deep inside: the primal urge to build a Christmas tree. Right here, right now.

But beware: an ordinary Christmas tree will not do. You must build a Special Christmas Tree.

For the purposes of this problem, a Christmas Tree is simply a binary tree— that is, a connected, acyclic graph where each node has degree at most three.

So, what makes it Special?

You are given three integers $$$P$$$, $$$Q$$$, and $$$R$$$.

Suppose your Christmas Tree has $$$N$$$ nodes, labeled $$$1$$$ through $$$N$$$.

The following conditions must hold:

  • There are exactly $$$P$$$ pairs $$$(i, j)$$$, with $$$1 \le i \lt j \le N$$$, such that the distance between node $$$i$$$ and node $$$j$$$ is exactly $$$1$$$.
  • There are exactly $$$Q$$$ pairs $$$(i, j)$$$, with $$$1 \le i \lt j \le N$$$, such that the distance between node $$$i$$$ and node $$$j$$$ is exactly $$$2$$$.
  • There are exactly $$$R$$$ pairs $$$(i, j)$$$, with $$$1 \le i \lt j \le N$$$, such that the distance between node $$$i$$$ and node $$$j$$$ is exactly $$$3$$$.

Here, the distance between two nodes means the number of edges on the unique simple path between them.

Your task is to construct such a Special Christmas Tree, or declare that it is impossible.

Input

The input consists of multiple test cases.

The first line contains an integer $$$T$$$ ($$$1 \le T \le 1000$$$)— the number of test cases.

Each of the next $$$T$$$ lines contains three integers $$$P$$$, $$$Q$$$, and $$$R$$$ ($$$1 \le P \le 10^5$$$, $$$0 \le Q, R \le 10^6$$$) — the designated counts of pairs of nodes at distances $$$1$$$, $$$2$$$, and $$$3$$$, respectively.

The sum of $$$P$$$ over all test cases does not exceed $$$10^5$$$.

Output

For each test case:

Print a line with a single integer $$$N$$$ — the number of nodes in your tree.

Then print $$$N-1$$$ lines, each with two integers $$$u$$$ and $$$v$$$ ($$$1 \le u,v \le N$$$), denoting an edge between nodes $$$u$$$ and $$$v$$$.

If there are multiple possible trees, output any of them.

If no Special Christmas Tree exists, output $$$-1$$$.

Example
Input
3
2 1 0
5 6 4
3 7 1
Output
3
1 2
2 3
6
1 2
2 3
2 4
1 5
1 6
-1
Note

The Special Christmas Tree for the second test case can be visualized as:

Figure D.1: Example of the Christmas tree for the second test case.

There are $$$5$$$ node pairs with distance $$$1$$$: $$$(1,2)$$$, $$$(2,3)$$$, $$$(2,4)$$$, $$$(1,5)$$$, and $$$(1,6)$$$.

There are $$$6$$$ node pairs with distance $$$2$$$: $$$(1,3)$$$, $$$(1,4)$$$, $$$(2,5)$$$, $$$(2,6)$$$, $$$(3,4)$$$, and $$$(5,6)$$$.

There are $$$4$$$ node pairs with distance $$$3$$$: $$$(3,5)$$$, $$$(3,6)$$$, $$$(4,5)$$$, and $$$(4,6)$$$.

E. Extradimensional Cosmic Phenomenon
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The Intergalactic Cosmic Phenomenon Containment (ICPC) has reported a surge in Breach-Level Unstable Events (BLUEs) — rare extradimensional disturbances that manifest as rift points in local spacetime. If left unchecked, these anomalies may cascade into a full-scale reality fracture, erasing the timeline of the entire universe.

To address this crisis, the ICPC has deployed $$$N$$$ Anomaly Regulation Centers (ARCs). Each ARC must be assigned a set of BLUEs to stabilize, under the following conditions:

  • There are $$$X$$$ Type-Alpha BLUEs, each requiring exactly 1 unit of energy to stabilize.
  • There are $$$Y$$$ Type-Omega BLUEs, each requiring exactly 2 units of energy to stabilize.

Each BLUE must be assigned entirely to exactly one ARC (no splitting or sharing). An ARC may stabilize multiple BLUEs, but the total required energy for its assigned anomalies must be drawn from its own reservoir.

To maintain synchronization across containment protocols, the ICPC mandates that the energy loads be distributed as evenly as possible among the ARCs.

Your task is to determine the minimum possible energy imbalance, defined as the difference between the maximum energy assigned to any ARC and the minimum energy assigned to any ARC.

Input

The first line contains a single integer $$$T$$$ — the number of test cases. ($$$1 \le T \le 1000$$$)

The next $$$T$$$ lines each contain three integers $$$X, Y, N$$$. ($$$0 \le X, Y \le 10^9$$$, $$$2 \le N \le 10^6$$$) — the number of Type-Alpha BLUEs, the number of Type-Omega BLUEs, and the number of Anomaly Regulation Centers (ARCs).

Output

For each test case, output a single integer — the minimum possible difference between the maximum energy assigned to any ARC and the minimum energy assigned to any ARC.

Example
Input
5
2 2 3
1 4 3
3 2 3
0 5 3
3 0 3
Output
0
2
1
2
0
Note

In the first case, the distribution can be as follows:

  • The first ARC takes $$$2$$$ Type-Alpha BLUEs.
  • The second and third ARCs each take $$$1$$$ Type-Omega BLUE.
  • They all spent two energy units, so the difference is $$$0$$$.

In the second case, the distribution can be as follows:

  • The first ARC takes $$$1$$$ Type-Alpha BLUE and $$$1$$$ Type-Omega BLUE.
  • The second takes $$$2$$$ Type-Omega BLUEs.
  • The third takes $$$1$$$ Type-Omega BLUE.
  • The difference is $$$3$$$ (the first ARC) $$$- 1$$$ (the third ARC) $$$= 2$$$. It can be shown that this is the optimal assignment.

F. Flying Pig Borrowing Log
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

A certain high school requires students to read several selected books. Among those books, there is one outstanding book titled "Flying Pig".

There are $$$N$$$ students, numbered from $$$1$$$ to $$$N$$$, who are planning to read this book. There are $$$M$$$ days in a semester. The library opens every day for the entire semester, and the book is available from the beginning of the semester. The $$$i$$$-th student will visit the library the first time on day $$$b_i$$$ and will visit again on day $$$b_i + a_i, b_i + 2 \cdot a_i,\dots,b_i + x \cdot a_i$$$ where $$$1 \leq x$$$ and $$$b_i + x \cdot a_i \leq M$$$.

On day $$$d$$$, if a student visits the library and the book is available and the student has not read it before, the student borrows it and returns it exactly $$$c_i$$$ days later; that is, if the $$$i$$$-th student borrows the book on day $$$d$$$, it becomes available again on day $$$d + c_i$$$. If multiple students visit on the same day, the book is given to the student with the smallest number. A student may also borrow the book even if $$$d + c_i \gt M$$$, in which case the return is considered to happen after the $$$M$$$-th day.

For each student, print the day the student gets to borrow the book, or $$$-1$$$ if the student will not be able to borrow the book until the end of the semester.

Input

The first line contains two integers, $$$N$$$ and $$$M$$$ — the number of students and the number of days in the semester. $$$(1 \leq N, M \leq 100,000)$$$

The next $$$N$$$ lines contain three integers, $$$a_i, b_i,$$$ and $$$c_i$$$ — the numbers for the $$$i$$$-th student visitation pattern stated in the problem statement, and the duration of the $$$i$$$-th student borrowing. $$$(1 \leq a_i, b_i, c_i \leq M)$$$.

Output

Output one line with $$$N$$$ integers – the day student $$$1,2,3,\dots,N$$$ gets to borrow the book, or $$$-1$$$ if the student will not be able to borrow the book until the end of the semester.

Example
Input
3 10
4 2 3
3 4 1
5 2 1
Output
2 7 -1 
Note

Sample Explanation

Student $$$1$$$ visited the library on days $$$2$$$, $$$6$$$, and $$$10$$$.

Student $$$2$$$ visited the library on days $$$4$$$, $$$7$$$, and $$$10$$$.

Student $$$3$$$ visited the library on days $$$2$$$ and $$$7$$$.

On day $$$2$$$, students $$$1$$$ and $$$3$$$ visited the library, but student $$$1$$$ had a lower number, so the book was borrowed by student $$$1$$$.

On day $$$4$$$, student $$$2$$$ visited, but the book was not available.

On day $$$5$$$, student $$$1$$$ returned the book. The book became available again, but it was not borrowed since no one visited the library that day.

On day $$$7$$$, students $$$2$$$ and $$$3$$$ visited the library, but student $$$2$$$ had a lower number, so the book was borrowed by student $$$2$$$.

On day $$$8$$$, student $$$2$$$ returned the book. The book became available again, but it was not borrowed since no one visited the library that day.

On day $$$10$$$, students $$$1$$$ and $$$2$$$ visited the library, but both of them had already read the book, so it was not borrowed.

G. Gamer's Karma Farming Strat
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

After spending a long time collecting data and training his AI, Daeng confidently predicts that his mom will assign him $$$N$$$ household tasks to complete during the day.

Task $$$i$$$ is scheduled to take place during a specific time interval, starting at second $$$l_i$$$ and ending at second $$$r_i$$$ (inclusive). The task also has a karma value $$$k_i$$$. It is guaranteed that no two task intervals overlap with each other.

At the start of the day, Daeng's karma score is $$$0$$$. When the clock reaches the start time $$$l_i$$$ of a task, Daeng must make a choice:

  • Do the task: Daeng gains $$$k_i$$$ karma points. However, from the second $$$l_i$$$ to $$$r_i$$$, he is fully occupied and cannot do anything else.
  • Skip the task: Daeng may choose to ignore the task, but this is only allowed if his current karma score is at least $$$k_i$$$. In that case, his karma score decreases by $$$k_i$$$.

In addition to household tasks, Daeng wants to enjoy his favorite game as many times as possible throughout the day. Each game session lasts exactly $$$M$$$ seconds. While Daeng is playing, he cannot work on tasks and must be continuous once started. Also, he can only have one gaming session at a time.

Time during the day is measured from second $$$0$$$ up to second $$$86{,}399$$$, making exactly one full day. Since each task interval includes both its starting and ending seconds, if a task ends at time $$$r$$$, Daeng is free to begin another activity at time $$$r+1$$$. For example, if a game begins at second $$$0$$$, it will finish at second $$$M-1$$$.

Find the maximum number of game sessions Daeng can have on the day.

Input

The first line contains two integers $$$N$$$ and $$$M$$$ ($$$1 \leq N \leq 10{,}000$$$, $$$1 \leq M \leq 86{,}400$$$) — the number of tasks and the duration of one game session in seconds.

Each of the next $$$N$$$ lines contains three integers $$$l_i,\; r_i,\; k_i$$$ ($$$0 \leq l_i \leq r_i \lt 86{,}400$$$, $$$1 \leq k_i \leq 20{,}000$$$) — the start time, end time, and karma value of the $$$i$$$-th task.

It is guaranteed that no task intervals overlap. That is, for any integer $$$i$$$ and $$$j$$$ between $$$1$$$ to $$$N$$$, if $$$i \neq j$$$, then $$$min(r_i, r_j) \lt max(l_i, l_j)$$$.

Also, $$$\sum_{i=1}^{N} k_i \leq 20{,}000$$$.

Output

Print a single integer — the maximum number of game sessions Daeng can play during the day without violating the rules.

Examples
Input
3 1
0 1 1
2 4 1
6 10 1
Output
86395
Input
10 7
1 2 2
3 7 1
10 11 3
12 13 3
15 16 3
18 21 5
23 23 1
24 25 5
26 30 5
31 33 2
Output
12341
Note

Sample explanation

In the first example, Daeng must do task 1 since he initially has no karma points. Then he can choose whether or not to do task 2. The optimal choice is to do task 2 and skip task 3.

H. Halting Zero Permutation
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

A permutation of size $$$m$$$ is a sequence of $$$m$$$ positive integers containing each number from $$$1$$$ to $$$m$$$ exactly once. For example, $$$[1,4,5,3,2]$$$ is a permutation of size $$$5$$$, while $$$[1,1,4,3,5]$$$ and $$$[1,6,2,3,4]$$$ are not.

For an even-length sequence $$$[A_1, A_2, \ldots, A_{2t}]$$$, we define its power-product value ($$$\Lambda(A)$$$) as the product of terms obtained by taking each consecutive pair $$$(A_{2i-1}, A_{2i})$$$, raising the first element to the power of the second, and multiplying all such results together. Formally,

$$$$$$ \Lambda(A) = \prod_{i=1}^{t} A_{2i-1}^{\,A_{2i}} = (A_1^{A_2}) \cdot (A_3^{A_4}) \cdot (A_5^{A_6}) \cdot \ldots \cdot (A_{2t-1}^{A_{2t}}). $$$$$$

For example, if $$$A = (3,2,5,6,4,1)$$$, then $$$\Lambda(A) = 3^2 \cdot 5^6 \cdot 4^1 = 562500$$$

Next, we define a halting zero value of a number as equal to how many trailing zeros an integer has. For a positive integer $$$x$$$, let the halting zero function $$$\mho_0(x)$$$ be the number of zeros at the end of its decimal representation. Formally:

$$$$$$ \mho_0(x) = \max \{ k \in \mathbb{Z}_{\geq 0} : 10^k \mid x \}. $$$$$$

For example, $$$\mho_0(12000) = 3, \mho_0(907) = 0$$$

Your task is to find $$$ \max_{P} \mho_0(\Lambda(P))$$$ when $$$P$$$ is a permutation of size $$$2N$$$. Because the answer may be extremely large, output the result modulo $$$10^9+7$$$.

Input

The first line contains a single integer $$$T$$$ — the number of test cases. $$$(1 \le T \le 1000)$$$

Each of the next $$$T$$$ lines contains a single integer $$$N$$$. $$$(1 \le N \le 10^{12})$$$

Output

For each test case, output a single integer — the maximum value of $$$\mho_0(\Lambda(P))$$$ modulo $$$10^9+7$$$.

Example
Input
4
2
3
5
13
Output
0
6
17
142
Note

For $$$N = 3$$$ : Let $$$P = (5,6,4,3,2,1)$$$, then $$$\mho_0(\Lambda(P)) = \mho_0(5^6 \cdot 4^3 \cdot 2^1) = \mho_0(2,000,000) = 6$$$, which is the maximum value.

For $$$N = 5$$$ : Let $$$P = (4,2,3,6,5,9,1,7,10,8)$$$, then $$$\mho_0(\Lambda(P)) = \mho_0(4^2 \cdot 3^6 \cdot 5^9 \cdot 1^7 \cdot 10^8)$$$ $$$= \mho_0(2,332,800,000,000,000,000,000) = 17$$$, which is the maximum value.

L. Land of the Golden Butterflies
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The lord has vanished without a trace.

Inside a secluded castle, the royal family gathered to claim his inheritance. One by one, they perished—locked rooms, vanished alibis, headless corpses—until only two remained: Ange and Beatrice.

The lord's will was sealed within an epitaph. It was said that whoever deciphered it would become the rightful heir. Ange solved the riddle... but only a moment too late. At the end of the path, Beatrice was already waiting with a smile.

The inheritance is the family estate: a convex polygon within which stand two ancient landmarks. Yet Beatrice, in her magnanimity, offered Ange a chance to share the rule. The land will be divided by the following ritual:

  • A chord of the polygon is chosen uniformly at random. A chord is a straight line connecting two non-adjacent vertices of the polygon.
  • If at least one of the landmarks lies on the chord, or both landmarks fall on the same region after the partition, the chord is discarded and another is drawn.
  • Once a valid chord is found, the polygon is divided into two subregions.

Beatrice, having arrived first, always claims the larger half. Ange receives the smaller one.

Your task is to compute the expected difference in area between Beatrice's region and Ange's region.

Let $$$P = 10\,000\,000\,019$$$. P is a prime number. It can be shown that the answer can be expressed as an irreducible fraction $$$\frac{x}{y}$$$ where $$$x$$$ and $$$y$$$ are integers and $$$y \not\equiv 0 \pmod P$$$. Output the integer equal to $$$x\cdot y^{-1} \pmod P$$$. In other words, output such an integer $$$a$$$ that $$$0 \le a \lt P$$$ and $$$a\cdot y=x \pmod P$$$.

Input

The first line contains a single integer $$$N$$$ — the number of vertices of the polygon $$$(3 \leq N \leq 10^5)$$$.

Each of the next $$$N$$$ lines contains two integers $$$x_i, y_i$$$ $$$(-10^9 \leq x_i, y_i \leq 10^9)$$$, representing the coordinates of the polygon's vertices, given in clockwise order. The polygon is guaranteed to be convex , and no three consecutive vertices are collinear.

The last line contains four integers $$$x_p, y_p, x_q ,y_q$$$ $$$(-10^9 \leq x_p, y_p, x_q ,y_q \leq 10^9)$$$, representing the coordinates of the two landmarks, one at $$$(x_p,y_p)$$$ and another at $$$(x_q,y_q)$$$, which both are guaranteed to lie strictly inside the polygon.

Output

Print the answer modulo $$$10\,000\,000\,019$$$ in a single line. If it is impossible to select the chord to fit the criteria, print $$$-1$$$.

Examples
Input
7
0 0
-1 2
1 5
5 4
6 1
5 -1
2 -2
3 4 3 1
Output
11
Input
6
0 5
4 3
6 0
2 -1
0 0
-1 3
1 0 0 1
Output
5000000010
Input
3
10 0
0 0
5 10
3 1 7 3
Output
-1
Note

The polygon in the first test case can be visualized as follows:

Figure L.1: The polygon showing the two landmarks (inside points) and all chords that successfully separate them.

Depending on the language, the expected difference or other intermediate values can exceed the range of 32-bit or even 64-bit integers in worst cases. To avoid overflow:

  • C++: use __int128.
  • Java and Kotlin: use BigInteger from java.math.