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?
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 one line containing one integer $$$x$$$, denoting the minimum time cost among these $$$3$$$ plans.
14 12 18
12
1 1 45
1
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$$$.
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.
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 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.
100 1 51 50 1
4950
7 5 34 67 881 50 882 50 883 50 884 -50 89
951
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.
"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:
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:
Because of too many deadlines, Kiwi asked you to help her with the mission.
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:
It's guaranteed that the sum of $$$n$$$ and the sum of $$$q$$$ over all test cases doesn't exceed $$$2 \times 10 ^ 5$$$.
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).
25 71 1 1 2 12 3 51 5 31 2 42 2 52 1 51 1 52 1 53 611 12 132 1 12 1 22 1 31 2 142 2 32 1 2
NO YES NO YES YES YES YES YES NO
For the first sample test case, there are $$$7$$$ queries:
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.
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$$$.
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}$$$.
27 2 190.11 15 318 25.67 7.71 57.55 40.9610 8133.91 1 1100100100
0.00 0.00 154.67 0.00 173.70 19.03 0.00 0.00 0.00 0.00 0.00 0.00
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.
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:
$$$$$$ 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} $$$$$$
$$$$$$ m! = \begin{cases} 1, & \text{if } m = 0 \\ 1 \times 2 \times 3 \times \dots \times m, & \text{if } m \geq 1 \end{cases} $$$$$$
$$$$$$ 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$$$.
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})$$$.
For each test case, output one line containing one integer, denoting the value of the expression modulo $$$998244353$$$.
3351145141919810
9 15 516911908
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$$$:
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:
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
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.
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$$$.
For each test case, output one line containing one integer $$$x$$$, denoting the minimum operations you need to make all non-empty subsequences imbalanced.
24()))7)()()((
1 2
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.
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:
Assuming both OC and KP play optimally, determine who will win.
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$$$.
For each test case, output one line containing one string: either OC or KP, denoting the winner under optimal play.
34 42 1100000000 10
OC OC KP
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?
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. $$$$$$
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$$$.
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}$$$.
25 31 2 3 4 53 125 6 7
0.500000 0.000000
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.
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.
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 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}$$$.
4 3.141 230 -1-2 00 3
0.000
5 3.141 2.82852 -2-3 -31 11 -4-3 3
0.654
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:
![]() | ![]() |
| $$$0^{\circ}$$$ | $$$90^{\circ}$$$ |
![]() | ![]() |
| $$$180^{\circ}$$$ | $$$270^{\circ}$$$ |
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.
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:
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.
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.
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.
7 5 25 5 06
4 3 5 2 3 5 0 1 5 2 6 0 2
2 2 22 2 01
-1
4 9 94 9 06
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
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:
These are not the only ways to achieve the goal.
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).
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.
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).
24 6 9Most Stupid Technique6 6 4Failed System Test
YES NO
52 8 3My Solution TLE7 5 7Missing Snack Tragedy5 10 10Coins Collecting Foundation7 4 6Awkward Code Merges8 13 4Counting Combinatorial Bits
YES YES NO NO NO
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.
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.
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 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.
5 51 21 32 32 42 5
01111
8 91 26 73 73 55 81 42 42 31 6
00010100
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$$$:
Thus, the output is 01111.
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:
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.
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 $$$n$$$ lines. Each line should contain $$$4$$$ binary digits denoting the modified chart. Do not output any extra spaces or blank lines.
41011010010010010
1011 0000 1100 0011
2000110100100100100100100001100001101001000011110000110100001111000011010010100001
0011 0000 1100 0011 0100 0000 1110 0000 0011 1100 0011 1100 0011 0100 0011 1100 0011 0000 1100 0011
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.
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.
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.
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.
5 6 103 30 15 20 6
2
3 4 61 8 12
-1
4 9 75 8 14 21
0
For the first sample test case, one possible way to achieve the goal is:
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.