2025 Fujian Normal University Programming Contest
A. One Must Imagine Time Tight,
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Recently, OC, KP, and XW teamed up to participate in the $$$\infty$$$-th China Collegiate Programming Contest in another world. But unfortunately, they woke up too late to catch up with their plan, and the hotel they booked was far away from the competition venue due to heavy expenses, so they decided to take a taxi directly.

According to the navigation, there were $$$3$$$ candidate plans for them to choose from, with time costs $$$a$$$, $$$b$$$, and $$$c$$$. As you can see, the time may be tight, so they need to pick out the plan with the minimum time cost. Can you help them?

Input

The first line contains $$$3$$$ integers $$$a, b, c$$$ $$$(1 \leq a, b, c \leq 60)$$$, denoting the time cost of the $$$3$$$ plans.

Output

Output one line containing one integer $$$x$$$, denoting the minimum time cost among these $$$3$$$ plans.

Examples
Input
14 12 18
Output
12
Input
1 1 45
Output
1
Note

For the first sample test case, the time cost of the $$$3$$$ plans was $$$14, 12, 18$$$ respectively. The $$$2$$$-nd plan had the minimum time cost, so you need to choose it and output its time cost $$$12$$$.

For the second sample test case, you can choose the $$$1$$$-st or the $$$2$$$-nd plan since they share the same time cost, and output any of their time costs $$$1$$$.

B. Uchiage Hanabi
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

One forgotten night, KP was feeling down while staring at his computer. Seeing this, LW decided to cheer him up with something special.

LW brought KP to a straight road with $$$n$$$ points; point $$$i$$$ is at position $$$i$$$, respectively. At the beginning of each time, KP can choose a position to teleport. But he can only teleport no more than $$$d$$$ distance each time and does not exceed the boundary (i.e. if KP is at position $$$x$$$ at the end of time $$$i - 1$$$, then at the beginning of time $$$i$$$, he can teleport to any position in $$$[\max(1, x - d), \min(n, x + d)]$$$, even between two points). Specially, at the beginning of time $$$1$$$, KP can teleport to either point $$$1$$$ or point $$$n$$$.

Unlike usual, there will be $$$m$$$ fireworks shows taking place on some points tonight. At the end of time $$$t_i$$$, a fireworks show will happen at point $$$a_i$$$. If KP is currently at point $$$x$$$, then he will gain $$$b_i \cdot |x - a_i|$$$ happiness. Note that happiness may be negative.

Help LW calculate the maximum total happiness KP can gain after all the fireworks shows.

Input

The first line contains three integers $$$n, m, d$$$ $$$(1 \leq d \leq n \leq 10^5, 1 \leq m \leq 500)$$$, denoting the number of points on the road, the number of fireworks shows, and the maximum distance KP can move in each time unit.

For the following $$$m$$$ lines, the $$$i$$$-th line contains three integers $$$a_i, b_i, t_i$$$ $$$(1 \leq a_i \leq n, 1 \leq |b_i|, t_i \leq 10^9)$$$, denoting the parameters of a fireworks show as described.

It's guaranteed that $$$t_i$$$ is non-decreasing, i.e. $$$t_{i-1} \leq t_i$$$ is guaranteed for all $$$1 \lt i \leq m$$$.

Output

Output a line containing one integer, denoting the maximum total happiness KP can gain after all fireworks shows. It can be proved that the answer will always be an integer.

Examples
Input
100 1 5
1 50 1
Output
4950
Input
7 5 3
4 67 88
1 50 88
2 50 88
3 50 88
4 -50 89
Output
951
Note

For the first test case, KP can initially teleport to $$$1$$$ or $$$n$$$ at the beginning of time $$$1$$$. Since the only firework will happen at point $$$1$$$, he chooses to start with $$$n$$$ (i.e. $$$100$$$), and will gain $$$50 \times |100 - 1| = 4950$$$ happiness.

C. Sequential Sequence
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

"This time, I want to connect not just the people around me, but the whole world," Kiwi once had a small dream about linking.

If she applies that dream to a certain sequence $$$s_1, s_2, \ldots s_n$$$, then a criterion sequential emerges:

  1. Let $$$s'$$$ be a copy of $$$s$$$, then sort $$$s'$$$ in ascending order;
  2. If $$$s'_i - s'_{i - 1} = 1$$$ satisfies for all $$$i \in [2, n]$$$, then we call the sequence $$$s$$$ sequential.

One day, she is given a sequence $$$a$$$ of length $$$n$$$, and her mission is to process $$$q$$$ queries. Each query is one of the following types:

  • $$$1~x~y$$$: change $$$a_x$$$ to $$$y$$$, i.e., $$$a_x := y$$$;
  • $$$2~l~r$$$: check whether the continuous subsequence $$$a_l, a_{l + 1}, \ldots, a_r$$$ is sequential.

Because of too many deadlines, Kiwi asked you to help her with the mission.

Input

There are multiple test cases. The first line of the input contains a single integer $$$t$$$ $$$(1 \leq t \leq 100)$$$, denoting the number of test cases. For each test case:

The first line contains two integers $$$n$$$, $$$q$$$ $$$(1 \leq n, q \leq 10 ^ 5)$$$, denoting the length of $$$a$$$ and the number of queries.

The second line contains $$$n$$$ integers $$$a_i$$$ $$$(1 \leq a_i \leq 10 ^ 5)$$$.

For the following $$$q$$$ lines, the $$$i$$$-th line contains three integers, denoting the $$$i$$$-th query. Each query is one of the following types:

  • $$$1~x_i~y_i$$$ $$$(1 \leq x_i \leq n, 1 \leq y_i \leq 10 ^ 5)$$$;
  • $$$2~l_i~r_i$$$ $$$(1 \leq l_i \leq r_i \leq n)$$$.

It's guaranteed that the sum of $$$n$$$ and the sum of $$$q$$$ over all test cases doesn't exceed $$$2 \times 10 ^ 5$$$.

Output

For each query of type $$$2$$$, output YES if the sequence is sequential. Otherwise, output NO.

You may print each letter in any case (Yes, yes, Yes will all be recognized as a positive answer,  No, no, nO will all be recognized as a negative answer).

Example
Input
2
5 7
1 1 1 2 1
2 3 5
1 5 3
1 2 4
2 2 5
2 1 5
1 1 5
2 1 5
3 6
11 12 13
2 1 1
2 1 2
2 1 3
1 2 14
2 2 3
2 1 2
Output
NO
YES
NO
YES
YES
YES
YES
YES
NO
Note

For the first sample test case, there are $$$7$$$ queries:

  1. Check the subsequence $$$1, 2, 1$$$. After sorting, $$$s'=[1, 1, 2]$$$. Absolutely, $$$s_2 - s_1 = 0$$$, so the subsequence is not sequential;
  2. Change $$$a_5$$$ to $$$3$$$. After that, the sequence became: $$$1, 1, 1, 2, 3$$$;
  3. Change $$$a_2$$$ to $$$4$$$. After that, the sequence became: $$$1, 4, 1, 2, 3$$$;
  4. Check the subsequence $$$4, 1, 2, 3$$$. The subsequence satisfies the criterion, and it is sequential;
  5. $$$\ldots$$$

D. Where's My Money?
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

After struggling with plan choosing in One Must Imagine Time Tight, OC, KP, and XW decided to settle things a different way: by splitting bills.

Everyone likes AA, which means that all bills are split equally, but it is really inconvenient to pay separately every time they check out. Therefore, they decided that one person would pay all the bills upfront each time and share the total amount in a WeChat group, and they would settle up together after returning to school.

Fortunately, they all travel in groups of three, so it's guaranteed that no two people split the bills separately.

However, the journey back from the other world was exhausting, and the three returned to school feeling drained and unable to struggle with the accounts. Can you help them?

Formally, given $$$3$$$ arrays of floating-point numbers $$$a, b, c$$$, denoting the lists of bills paid by OC, KP, and XW respectively, for any two different people $$$A$$$ and $$$B$$$, output the amount $$$A$$$ needs to transfer to $$$B$$$ so that in the end, everyone has split the bills equally.

You do not need to minimize the total sum of all money transfers. In other words, meaningless transfers are allowed.

Input

There are multiple test cases. The first line of the input contains an integer $$$t$$$ $$$(1 \leq t \leq 100)$$$, denoting the number of test cases. For each test case:

The first line contains three integers $$$n, m, p$$$ $$$(0 \leq n, m, p \leq 10 ^ 3)$$$.

The second line contains $$$n$$$ positive floating-point numbers $$$a_i$$$ $$$(0 \lt a_i \leq 10 ^ 3)$$$, denoting the lists of bills paid by OC.

The third line contains $$$m$$$ positive floating-point numbers $$$b_i$$$ $$$(0 \lt b_i \leq 10 ^ 3)$$$, denoting the lists of bills paid by KP.

The fourth line contains $$$p$$$ positive floating-point numbers $$$c_i$$$ $$$(0 \lt c_i \leq 10 ^ 3)$$$, denoting the lists of bills paid by XW.

It's guaranteed that the decimal places of the floating-point numbers do not exceed $$$2$$$.

Output

Define $$$A \rightarrow B$$$ as the amount $$$A$$$ needs to transfer to $$$B$$$.

For each test case, output one line containing $$$6$$$ floating-point numbers, denoting the amounts that: OC $$$\rightarrow$$$ KP, OC $$$\rightarrow$$$ XW, KP $$$\rightarrow$$$ OC, KP $$$\rightarrow$$$ XW, XW $$$\rightarrow$$$ OC, XW $$$\rightarrow$$$ KP.

Note that negative amounts of transfer are not allowed.

Your answer will be accepted if after transferring, the absolute error between every two people's payment does not exceed $$$10^{-2}$$$.

Example
Input
2
7 2 1
90.11 15 318 25.67 7.71 57.55 40.96
10 81
33.9
1 1 1
100
100
100
Output
0.00 0.00 154.67 0.00 173.70 19.03 
0.00 0.00 0.00 0.00 0.00 0.00 
Note

For the first sample test case, the total amount of payment is $$$679.9$$$, and the optimal choice is $$$KP \rightarrow OC = 135.63, XW \rightarrow OC = 192.73$$$. But you do not need to minimize the total amount of transfers, so the sample given is also acceptable.

For the second sample test case, everyone has exactly split the bills equally, so no one owes anyone else.

E. Binary Banter: Counting Combinatorial Bits
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Given a positive integer $$$n$$$, compute the value of the following expression modulo $$$998244353$$$:

$$$$$$ \sum_{i=0}^n\sum_{j=0}^i\left(C_i^j \bmod 2\right) $$$$$$

Where:

  • The binomial coefficient $$$C_i^j$$$ is defined as:

    $$$$$$ C_i^j = \begin{cases} \frac{i!}{j!(i - j)!}, & \text{if } 0 \leq j \leq i \\ 0, & \text{if } j \gt i \end{cases} $$$$$$

  • The factorial $$$m!$$$ is defined as the product of all positive integers from $$$1$$$ to $$$m$$$:

    $$$$$$ m! = \begin{cases} 1, & \text{if } m = 0 \\ 1 \times 2 \times 3 \times \dots \times m, & \text{if } m \geq 1 \end{cases} $$$$$$

  • The modulo operation $$$x \bmod y$$$ returns the remainder when $$$x$$$ is divided by $$$y$$$. For example:

    $$$$$$ 5 \bmod 2 = 1,\quad 8 \bmod 3 = 2,\quad 7 \bmod 7 = 0 $$$$$$

You need to output the value of the expression modulo $$$998244353$$$.

Input

There are multiple test cases. The first line of the input contains a single integer $$$t$$$ $$$(1 \leq t \leq 3 \times 10^5)$$$, denoting the number of test cases. For each test case:

The first and only line contains one integer $$$n$$$ $$$(1 \leq n \leq 10^{18})$$$.

Output

For each test case, output one line containing one integer, denoting the value of the expression modulo $$$998244353$$$.

Example
Input
3
3
5
1145141919810
Output
9
15
516911908
Note

For the first sample test case, $$$n = 3$$$, so you need to compute the following expression:

$$$$$$ \sum_{i=0}^{3} \sum_{j=0}^{i} \left( C_i^j \bmod 2 \right) $$$$$$

Let's analyze each row of binomial coefficients modulo $$$2$$$:

  • $$$i = 0$$$: $$$C_0^0 = 1 \Rightarrow 1 \bmod 2 = 1$$$
  • $$$i = 1$$$: $$$C_1^0 = 1$$$, $$$C_1^1 = 1 \Rightarrow 1 + 1 = 2$$$
  • $$$i = 2$$$: $$$C_2^0 = 1$$$, $$$C_2^1 = 2$$$, $$$C_2^2 = 1 \Rightarrow 1 + 0 + 1 = 2$$$
  • $$$i = 3$$$: $$$C_3^0 = 1$$$, $$$C_3^1 = 3$$$, $$$C_3^2 = 3$$$, $$$C_3^3 = 1 \Rightarrow 1 + 1 + 1 + 1 = 4$$$

So the total sum is $$$1 + 2 + 2 + 4 = 9$$$. And you need to output $$$9 \bmod 998244353 = 9$$$.

For the second sample test case, $$$n = 5$$$, so you need to compute the following expression:

$$$$$$ \sum_{i=0}^{5} \sum_{j=0}^{i} \left( C_i^j \bmod 2 \right) $$$$$$

Similarly:

  • $$$i = 0$$$: $$$1$$$
  • $$$i = 1$$$: $$$1\ 1$$$ $$$\Rightarrow$$$ sum = $$$3$$$
  • $$$i = 2$$$: $$$1\ 0\ 1$$$ $$$\Rightarrow$$$ sum = $$$5$$$
  • $$$i = 3$$$: $$$1\ 1\ 1\ 1$$$ $$$\Rightarrow$$$ sum = $$$9$$$
  • $$$i = 4$$$: $$$1\ 0\ 0\ 0\ 1$$$ $$$\Rightarrow$$$ sum = $$$11$$$
  • $$$i = 5$$$: $$$1\ 1\ 0\ 0\ 1\ 1$$$ $$$\Rightarrow$$$ sum = $$$15$$$

Final result: $$$(1 + 2 + 2 + 4 + 2 + 4) \bmod 998244353 = 15$$$

For the third sample test case, I have a brilliant explanation, but the space here is too small to writ

F. Imbalanced Bracket
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Once OC received a challenge from his memory fragments, which aroused his curiosity:

"You are given one bracket sequence $$$s$$$ with length $$$n$$$, answer the minimum operations you need to make all non-empty subsequences$$$^\dagger$$$ imbalanced$$$^\ddagger$$$.

Define that your one operation is to select $$$i \in [1, n]$$$ and change $$$s_i$$$ to another bracket."

But he is too busy beating the deadline, so he asked you to help him.

$$$^\dagger$$$ A sequence $$$b$$$ is a subsequence of sequence $$$a$$$ if $$$b$$$ can be obtained by deleting several (possibly, zero or all) elements from $$$a$$$. For example, $$$(()$$$, $$$()$$$, and $$$())$$$ are some subsequences of $$$()()$$$.

$$$^\ddagger$$$ A sequence is called imbalanced if you cannot turn it into a valid math expression by adding characters $$$+$$$ and $$$1$$$. For example, sequences $$$)($$$, $$$(()$$$, and $$$(()))($$$ are imbalanced, while $$$(())()$$$, $$$()$$$, and $$$(()(()))$$$ are not.

Input

There are multiple test cases. The first line of the input contains a single integer $$$t$$$ $$$(1 \leq t \leq 100)$$$, denoting the number of test cases. For each test case:

The first line contains a single integer $$$n$$$ $$$(1 \leq n \leq 2 \times 10 ^ 5)$$$.

The second line contains a string $$$s$$$ with length $$$n$$$, denoting the given bracket sequence.

It's guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$2 \times 10 ^ 5$$$.

Output

For each test case, output one line containing one integer $$$x$$$, denoting the minimum operations you need to make all non-empty subsequences imbalanced.

Example
Input
2
4
()))
7
)()()((
Output
1
2
Note

For the first sample test case, you can perform $$$1$$$ operation on $$$1$$$, changing $$$s$$$ to $$$))))$$$.

For the second sample test case, you can perform $$$2$$$ operations on $$$3, 5$$$, changing $$$s$$$ to $$$)(((((($$$.

These are not the only ways to satisfy the constraints.

G. Still No Money?
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

After struggling with bill splitting in Where's My Money?, OC and KP decided to settle things a different way: by having a barbecue. But unfortunately, XW didn't come this time — probably still struggling with floating-point errors.

When it came time to pay the bill, they still couldn't agree on a fair method. So, as any reasonable programmers would, they decided to play a game with the leftover bamboo skewers to determine who pays.

The rules are as follows:

  • There are initially $$$x$$$ bamboo skewers, and they agree on a positive integer $$$k$$$.
  • OC and KP take turns, with OC going first.
  • On each turn, a player must remove at least $$$1$$$ and at most $$$k$$$ skewers. After each move, $$$k$$$ decreases by $$$1$$$. (Note that if $$$k = 0$$$, no further moves can be made.)
  • The player who cannot make a move loses.

Assuming both OC and KP play optimally, determine who will win.

Input

There are multiple test cases. The first line of the input contains an integer $$$t$$$ $$$(1 \leq t \leq 10^5)$$$, denoting the number of test cases. For each test case:

The first and only line contains two integers $$$x$$$ and $$$k$$$ $$$(1 \le x, k \le 10^{18})$$$, denoting the initial number of skewers and the starting value of $$$k$$$.

Output

For each test case, output one line containing one string: either OC or KP, denoting the winner under optimal play.

Example
Input
3
4 4
2 1
100000000 10
Output
OC
OC
KP
Note

For the first sample test case, OC can take all $$$4$$$ skewers on their first move. Then it's KP's turn, but there are no skewers left, so KP cannot make a move. OC wins.

For the second sample test case, OC can only take $$$1$$$ skewer on the first move (since $$$k = 1$$$). After that, $$$k$$$ becomes $$$0$$$, and it's KP's turn — but with $$$k = 0$$$, no move is allowed. OC wins again.

For the third sample test case, obviously they will never exhaust all $$$10^8$$$ skewers before $$$k$$$ reaches $$$0$$$. Since $$$k$$$ decreases by $$$1$$$ after each move, there will be exactly $$$10$$$ moves in total. And OC moves first; therefore, the $$$10$$$th and final move belongs to KP, so KP wins.

But the real problem is, who's going to pay for these $$$100$$$ million skewers?

H. Yet Another Tree Problem
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$n$$$ trees along a road. The height of the $$$i$$$-th tree is $$$a_i$$$.

In one operation, you can select a tree with positive height and cut it one unit of wood. You must perform exactly $$$s$$$ operations.

After $$$s$$$ operations, consider the set of trees with positive height. You need to output the minimum possible $$$\text{variance}^{\dagger}$$$ of the heights of these remaining trees.

$$$^{\dagger}$$$ The $$$\text{variance}$$$ of a sequence $$$b_1, b_2, \ldots, b_k$$$ is defined as:

$$$$$$ \text{variance} = \frac{1}{k} \sum_{i=1}^{k} (b_i - \overline{b})^2 $$$$$$

where $$$\overline{b}$$$ is the average of the sequence, s.t. $$$\overline{b} = \frac{b_1 + b_2 + \dots + b_k}{k}$$$.

For example, for the sequence $$$\{3,5,1,4,2\}$$$:

$$$$$$ \overline{b} = 3, \quad \text{variance} = \frac{1}{5}((3-3)^2 + (5-3)^2 + (1-3)^2 + (4-3)^2 + (2-3)^2) = 2. $$$$$$

Input

There are multiple test cases. The first line of the input contains one integer $$$t$$$ $$$(1 \leq t \leq 100)$$$, denoting the number of test cases. For each test case:

The first line contains two integers $$$n$$$ and $$$s$$$ $$$(1 \leq n \leq 2 \times 10^5, 1 \leq s \leq 10^9)$$$, denoting the number of trees and the number of units of wood you must cut.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ $$$(1 \leq a_i \leq 10^6)$$$, denoting the initial heights of the trees.

It's guaranteed that $$$s \lt \sum a_i$$$, so there will always be at least one tree with positive height after all cuts, and it's guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \times10^5$$$.

Output

For each test case, output one real number in one line, denoting the minimal possible variance of the remaining trees' heights after the cuts.

Your answer will be considered correct if it has an absolute or relative error not exceeding $$$10^{-4}$$$. Formally, suppose that your answer is $$$a$$$ and the jury's answer is $$$b$$$, your answer is accepted if and only if $$$\frac{\left| a - b \right|}{\max(1, |b|)} \le 10^{-4}$$$.

Example
Input
2
5 3
1 2 3 4 5
3 12
5 6 7
Output
0.500000
0.000000
Note

For the first test case, one optimal strategy is to cut tree 1 once and tree 5 twice. The remaining trees have heights $$$\{2,3,4,3\}$$$, and their variance is $$$0.5$$$.

For the second test case, one optimal strategy is to cut tree 1 five times and tree 3 seven times. The remaining trees have heights $$$\{6\}$$$, and the variance is $$$0$$$.

It can be proved that no other strategy yields a smaller variance.

I. DJ Mr. Spin
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

OC once took notice of a game called Reteeee. The core element of this game is spinning, which aroused his curiosity. To simplify, the game can be described as follows:

Assume there exists a rectangular plane coordinate system with the origin at $$$(0, 0)$$$. On this plane, there is a circle of radius $$$r$$$, centered at the origin. Inside the circle, there are $$$n$$$ distinct points $$$(x_i, y_i)$$$. You will have a point $$$P$$$ placed at the origin initially.

At the beginning of the game, the circle starts spinning counterclockwise at a speed of $$$v_1$$$ radians per second, and the points inside the circle spin along with it (around the center of the circle, at the same speed).

At time $$$t$$$, $$$P$$$ starts moving towards the positive X-axis at a speed of $$$v_2$$$ units per second. If vector $$$OP$$$ intersects a point, the point will disappear, and you will get $$$1$$$ point. The game ends as soon as $$$P$$$ intersects the circle.

Your task is to determine the minimum $$$t$$$ to achieve the maximum score.

Input

The first line contains three floating-point numbers $$$r, v_1, v_2$$$ $$$(1 \leq r, v_1, v_2 \leq 2 \times 10^5)$$$, denoting the radius of the circle, and the speed of the circle and $$$P$$$ respectively.

The second line contains one integer $$$n$$$ $$$(1 \leq n \leq 10^5)$$$, denoting the number of points.

For the following $$$n$$$ lines, the $$$i$$$-th line contains two integers $$$x_i, y_i$$$ $$$(0 \lt x_i^2 + y_i^2 \lt r^2)$$$, denoting the $$$i$$$-th point inside the circle.

It's guaranteed that $$$\frac{2 \pi}{v_1} \gt \frac{r}{v_2}$$$, and the points are distinct.

It's also guaranteed that the decimal places of the floating-point numbers do not exceed $$$3$$$.

Output

Output one line containing one floating-point number $$$t$$$, denoting the minimum time for $$$P$$$ to start moving and achieve the maximum score.

Your answer will be accepted if the absolute error between your answer and the standard answer does not exceed $$$10^{-3}$$$.

Examples
Input
4 3.141 2
3
0 -1
-2 0
0 3
Output
0.000
Input
5 3.141 2.828
5
2 -2
-3 -3
1 1
1 -4
-3 3
Output
0.654
Note

For the first example, $$$t = 0.000$$$. Here, $$$v_1$$$ is treated as $$$\pi$$$ (approximated). Let's simulate this according to the degree the circle has spun:

  1. $$$0^{\circ}$$$, $$$P$$$ starts moving, $$$A(0, -1), B(-2, 0), C(0, 3), P(0, 0)$$$.
    $$$0^{\circ}$$$$$$90^{\circ}$$$
  2. $$$90^{\circ}$$$, $$$A(1, 0), B(0, -2), C(-3, 0), P(1, 0)$$$. Vector $$$OP$$$ intersects point $$$A$$$, $$$A$$$ disappears, and you get $$$1$$$ point.
  3. $$$180^{\circ}$$$, $$$B(2, 0), C(0, -3), P(2, 0)$$$. Vector $$$OP$$$ intersects point $$$B$$$, $$$B$$$ disappears, and you get $$$1$$$ point.
    $$$180^{\circ}$$$$$$270^{\circ}$$$
  4. $$$270^{\circ}$$$, $$$C(3, 0), P(3, 0)$$$. Vector $$$OP$$$ intersects point $$$C$$$, $$$C$$$ disappears, and you get $$$1$$$ point.
  5. $$$360^{\circ}$$$, $$$P(4, 0)$$$. Vector $$$OP$$$ intersects the circle, the game ends.

For the second example, the optimal choice is to start moving when it will finally intersect the $$$4$$$-th point $$$(1, -4)$$$ and the circle at the same time.

J. Spirit of Cola.
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

After struggling with the bamboo skewers game in Still No Money?, OC, KP, and XW decided to settle things a different way: by drinking cola.

But unfortunately, again, the cola in this world has a spirit protecting it. The spirit has posed a challenge: they must manipulate the cola in three cups to reach a specific amount $$$t$$$.

The three cups have capacities $$$c_1$$$, $$$c_2$$$, and $$$c_3$$$ liters, respectively. Initially, the cups contain $$$w_1$$$, $$$w_2$$$, and $$$w_3$$$ liters of cola. They are allowed to use two types of operations sanctioned by the spirit:

  1. Choose two different cups $$$i$$$ and $$$j$$$, and pour $$$min(w_i, c_j - w_j)$$$ liters of cola from cup $$$i$$$ to $$$j$$$. In other words, pour cola from cup $$$i$$$ to $$$j$$$ until cup $$$j$$$ is full, or cup $$$i$$$ has run out of cola.
  2. Choose one non-empty cup that has the minimum liters of cola and turn it into sugar-free. The spirit hates sugar-free cola and will make the cup empty instantly.

To satisfy the spirit, their goal is to find out a way to make at least one cup have exactly $$$t$$$ liters of cola and minimize the number of operations. But take it easy; if you can prove that there is no way to achieve the goal, just tell the spirit.

Input

The first line contains three integers $$$c_1, c_2, c_3$$$ $$$(1 \leq c_1, c_2, c_3 \leq 300)$$$, denoting the capacities of the three cups.

The second line contains three integers $$$w_1, w_2, w_3$$$ $$$(0 \leq w_1, w_2, w_3 \leq 300, w_i \leq c_i)$$$, denoting the initial amount of cola in the three cups.

The third line contains one integer $$$t$$$ $$$(0 \leq t \leq 300)$$$, denoting the target amount of cola they need to achieve.

Output

If it is possible to achieve the goal, first output one line containing one integer $$$n$$$, denoting the number of operations. Then output $$$n$$$ lines, the $$$i$$$-th line containing three integers, denoting the amount of cola in the three cups after the $$$i$$$-th operation. If there are multiple ways, output any of them.

Otherwise, output $$$-1$$$ instead.

Examples
Input
7 5 2
5 5 0
6
Output
4
3 5 2
3 5 0
1 5 2
6 0 2
Input
2 2 2
2 2 0
1
Output
-1
Input
4 9 9
4 9 0
6
Output
15
0 9 4
4 5 4
0 5 8
4 1 8
3 1 9
3 0 9
0 3 9
4 3 5
0 7 5
4 7 1
2 9 1
2 9 0
0 9 2
4 5 2
0 5 6
Note

For the first sample test case, the initial state is $$$5, 5, 0$$$, and the target amount is $$$6$$$. To achieve the goal, you can perform the following $$$4$$$ operations:

  1. Cup $$$1$$$ $$$\rightarrow$$$ Cup $$$3$$$.
  2. Make Cup $$$3$$$ empty.
  3. Cup $$$1$$$ $$$\rightarrow$$$ Cup $$$3$$$.
  4. Cup $$$2$$$ $$$\rightarrow$$$ Cup $$$1$$$.

These are not the only ways to achieve the goal.

K1. MST(a.k.a. Most Shortened Terms)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

During a programming contest, Mr. Shocking Tale (a.k.a. MST) was accused of stealing code. To prove his innocence, he shouted: "My algorithm is original! It's literally called M... S... T...!"

The judges, however, noticed that every time he wrote "MST", the three-word expansion changed randomly. Was this a clever trick or just chaos?

One judge even snorted: "Yesterday it was Mangoes Squeeze Time, today it's Mice Sing Telepathically... Next, you'll say it's Minimum Spanning Tree!"

Whatever, to prove his correctness, given three words, determine if their initials form MST (i.e., each word starts with M, S, T in order).

Input

There are multiple test cases. The first line of the input contains a single integer $$$t$$$ $$$(1 \leq t \leq 100)$$$, denoting the number of test cases. For each test case:

The first line contains three integers $$$n, m, p$$$ $$$(1 \leq n, m, p \leq 20)$$$, denoting the length of the given three words.

The second line contains three strings consisting of uppercase and lowercase letters, denoting the given three words.

It's guaranteed that the initials of the three words are uppercase letters.

Output

For each test case, output YES if their initials form MST. Otherwise, output NO.

You may print each letter in any case (Yes, yes, Yes will all be recognized as a positive answer,  No, no, nO will all be recognized as a negative answer).

Examples
Input
2
4 6 9
Most Stupid Technique
6 6 4
Failed System Test
Output
YES
NO
Input
5
2 8 3
My Solution TLE
7 5 7
Missing Snack Tragedy
5 10 10
Coins Collecting Foundation
7 4 6
Awkward Code Merges
8 13 4
Counting Combinatorial Bits
Output
YES
YES
NO
NO
NO
Note

For the first sample test case, the initials of the first three words form MST, but the next three words form FST.

The sample cases here are solely intended to aid understanding of the problem. Any resemblance is purely coincidental.

K2. MST(a.k.a. Most Stupid Technique)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

During a programming contest, Mr. Search Tree (a.k.a. MST) forgot how to implement Kruskal's and Prim's algorithms. In a moment of desperation, he wrote a DFS that always follows the smallest available edge first. Strangely enough, it passed.

Now he wonders: for which starting nodes does his "Most Stupid Technique" accidentally produce a correct minimum spanning tree$$$^\dagger$$$ ?

Formally, given a connected undirected graph with $$$n$$$ nodes and $$$m$$$ edges, the $$$i$$$-th edge has weight $$$i$$$, and here is the algorithm he used:

vis := array of n booleans
s := set of edges

function dfs(u):
vis[u] := true
for each edge (u, v) connected to u in increasing order of edge weight:
if not vis[v]:
add edge (u, v) to s
dfs(v)

function findMST(u):
reset vis to all false
clear the edge set s
dfs(u)
return s

In other words, findMST(u) performs a DFS starting from vertex $$$u$$$, always choosing the smallest-weight unvisited edge from the current node and includes it in the tree.

Although this always produces a spanning tree, it doesn't always yield a minimum one.

Your task is to determine, for each node $$$i$$$ from $$$1$$$ to $$$n$$$, whether findMST(i) returns a minimum spanning tree.

$$$^\dagger$$$ A minimum spanning tree (MST) of a connected undirected graph is a subset of the edges that forms a tree connecting all the vertices and has the minimum possible total edge weight among all such trees.

Input

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2 \leq n \leq 10^5, n - 1 \leq m \leq 2 \cdot 10^5$$$), denoting the number of vertices and edges.

For the following $$$m$$$ lines, the $$$i$$$-th line contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n, u_i \neq v_i$$$), denoting an undirected edge between $$$u_i$$$ and $$$v_i$$$.

The $$$i$$$-th edge ($$$1$$$-based index in input) has weight $$$i$$$.

It's guaranteed that the graph is connected and contains no duplicate edges.

Output

Output one line containing a binary string of length $$$n$$$.

The i-th character should be '$$$1$$$'(without quotes) if the tree produced by running the algorithm above starting from node i is a minimum spanning tree, and '$$$0$$$'(without quotes) otherwise.

Examples
Input
5 5
1 2
1 3
2 3
2 4
2 5
Output
01111
Input
8 9
1 2
6 7
3 7
3 5
5 8
1 4
2 4
2 3
1 6
Output
00010100
Note

The sample case is shown below:

The graph for the sample

The only minimum spanning tree (MST) of this graph includes the edges with weights $$$1$$$, $$$2$$$, $$$4$$$, and $$$5$$$, which has a total edge weight of 12.

We simulate the algorithm findMST(u) for each $$$u$$$ from $$$1$$$ to $$$5$$$:

  • findMST(1) starts from node $$$1$$$ and visits edge $$$1$$$ first (to node $$$2$$$). Then at node $$$2$$$, the smallest unvisited adjacent edge is edge $$$3$$$ (to node $$$3$$$), so it is selected instead of edge $$$2$$$. As a result, edge $$$3$$$ (which has higher weight than edge $$$2$$$) is included in the result, and the resulting tree includes the edges with weights $$$1$$$, $$$3$$$, $$$4$$$, and $$$5$$$, which has a total edge weight of 13; so it doesn't construct the MST of the graph.
  • findMST(2), findMST(3), findMST(4), and findMST(5) all happen to construct the correct MST.

Thus, the output is 01111.

L. We Luv Stamina
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

No, we don't luv stamina; we luv jumptrills!

After being tortured by three hours of handstream practice, the desperate XW is begging you to write a program that converts a given stream chart into a purely jumptrills chart.

Let's describe your task in formal terms. Note that some definitions in this problem may differ from those used in real 4-key rhythm games.

A chart is an $$$n \times 4$$$ binary matrix. Let $$$c_{i,j}$$$ denote the element in the $$$i$$$-th row and $$$j$$$-th column. Here, $$$c_{i,j} = 1$$$ means there is a note at that position, and $$$c_{i,j} = 0$$$ means it is empty. The given chart is guaranteed to satisfy that no column has two consecutive notes, i.e. for all $$$1 \lt i \leq n$$$ and $$$1 \leq j \leq 4$$$, we have $$$c_{i-1,j} \times c_{i,j} = 0$$$.

While playing the chart, you hit notes in columns 1 and 2 with your left hand, and notes in columns 3 and 4 with your right hand. To make the chart more playable, XW wants to ensure that no hand is required to hit notes in two consecutive rows. To achieve this, he needs you to perform the following operation:

  • Check all rows in reverse order: from row $$$n-1$$$ down to row $$$1$$$.
  • For the current row $$$i$$$:
    • If row $$$i+1$$$ has a note in column 1 or 2, and row $$$i$$$ also has a note in column 1 or 2, then move the note in row $$$i$$$ down by one row. (It can be proven that in this case, there is only one such note and the position below it is empty.)
    • Similarly, if row $$$i+1$$$ has a note in column 3 or 4, and row $$$i$$$ also has a note in column 3 or 4, move that note in row $$$i$$$ down by one row.

After applying the above transformation, the chart will be converted from a terrifying dense handstream chart into a friendly jumptrills chart. But XW doesn't know how to implement it. Can you help him?

Reading the sample might help you better understand the task.

Input

The first line contains a single integer $$$n$$$ $$$(1 \leq n \leq 10^3)$$$, denoting the number of rows in the chart.

The next $$$n$$$ lines each contain $$$4$$$ binary digits, denoting whether a note exists in each of the 4 columns of the $$$i$$$-th row.

It's guaranteed that no column has two consecutive '$$$1$$$'.

Output

Output $$$n$$$ lines. Each line should contain $$$4$$$ binary digits denoting the modified chart. Do not output any extra spaces or blank lines.

Examples
Input
4
1011
0100
1001
0010
Output
1011
0000
1100
0011
Input
20
0011
0100
1001
0010
0100
1000
0110
0001
1010
0100
0011
1100
0011
0100
0011
1100
0011
0100
1010
0001
Output
0011
0000
1100
0011
0100
0000
1110
0000
0011
1100
0011
1100
0011
0100
0011
1100
0011
0000
1100
0011
Note

For the first sample case:

In row $$$3$$$, both the left hand (column $$$1$$$) and the right hand (column $$$4$$$) are used. Since row $$$4$$$ had right-hand usage (column $$$3$$$), so the note in column $$$4$$$ is moved down to row $$$4$$$ .

In row $$$2$$$, the left hand (column $$$1$$$) is also used, so the note in column $$$1$$$ is moved down to row $$$3$$$ .

In row $$$1$$$, both hands are used again. But since no hand is used in row $$$2$$$ (Note that the original note in row $$$2$$$ has already been moved to row $$$3$$$), so the notes in row 1 weren't moved.

After these operations, no hand is used in two consecutive rows.

M. The Journey Onwards...
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

After struggling with pouring cola in Spirit of Cola, KP got tired and decided to try something exciting: parkour.

The parkour takes place in a city called Ascent. On arrival, KP acquired a new skill called Blask Pack, which can pop himself out a certain distance by using blask packs.

In Ascent, the parkour map turns out to be a straight line with distinct $$$n$$$ footholds; the $$$i$$$-th foothold is $$$a_i$$$ meters away from KP. KP can jump out at most $$$x$$$ meters or pop out at most $$$y$$$ meters by using the skill once.

Help him determine whether it is possible to reach the furthest foothold. If it is possible, find out the minimum number of times the skill is used.

Input

The first line contains three integers $$$n, x, y$$$ $$$(1 \leq n \leq 3000, 0 \leq x, y \leq 10^6)$$$, denoting the number of footholds and the max distance KP can jump and pop.

The second line contains $$$n$$$ distinct integers $$$a_i$$$ $$$(1 \leq a_i \leq 10^6)$$$, denoting the distance between KP and the footholds.

Output

If it is possible to reach the furthest foothold, output one line containing one integer, denoting the minimum number of times the skill is used.

Otherwise, output $$$-1$$$ instead.

Examples
Input
5 6 10
3 30 15 20 6
Output
2
Input
3 4 6
1 8 12
Output
-1
Input
4 9 7
5 8 14 21
Output
0
Note

For the first sample test case, one possible way to achieve the goal is:

  1. Jump out $$$6$$$ meters to reach foothold $$$5$$$;
  2. Use skill, pop out $$$9$$$ meters to reach foothold $$$3$$$;
  3. Jump out $$$5$$$ meters to reach foothold $$$4$$$;
  4. Use skill, pop out $$$10$$$ meters to reach the furthest foothold $$$2$$$.

For the second sample test case, it is impossible to reach the furthest foothold.

For the third sample test case, note that $$$x \geq y$$$ is possible, and this makes the skill useless.

These are not the only ways to achieve the goal.