2020, XIII Samara Regional Intercollegiate Programming Contest
A. Array's Hash
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Vasya has invented a new hash function of an array. It is calculated as follows. While the array has at least two elements, the first two elements, call them $$$a_1$$$ and $$$a_2$$$, are deleted, and the new element $$$a_2 - a_1$$$ is inserted to the beginning of the array. When the array has only one element, this number is a value of Vasya's hash function of this array.

Vasya has the array $$$a_1$$$, $$$a_2$$$,..., $$$a_n$$$. He performs $$$q$$$ operations of the following form: "increase all elements in the segment $$$[l_j, r_j]$$$ by $$$v_j$$$". After each operation he wants to know the value of Vasya's hash function of this array.

Input

The first line contains an integer $$$n$$$ ($$$1 \le n \le 500000$$$) — the size of the array.

The second line contains $$$n$$$ integers $$$a_i$$$ ($$$-10^9 \le a_i \le 10^9$$$) — the elements of the array.

The third line contains an integer $$$q$$$ ($$$1 \le q \le 200000$$$) — the number of operations.

Each of the next $$$q$$$ lines contains three integers $$$l_j$$$, $$$r_j$$$, $$$v_j$$$ ($$$1 \le l_j \le r_j \le n,~-10^9 \le v_j \le 10^9$$$) — the parameters of the $$$j$$$-th operation.

Output

Output $$$q$$$ lines. In the $$$j$$$-th line output one integer — the value of Vasya's hash function after the $$$j$$$-th operation.

Example
Input
7
4 2 -5 10 4 -2 6
4
2 4 -8
5 7 2
3 3 -1
3 7 3
Output
7
9
8
11

B. Bonuses on a Line
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$n$$$ bonuses on a line: the $$$i$$$-th bonus is located at the point $$$x_i$$$. All coordinates of all bonuses are distinct. You are located at the point with the coordinate 0. How many bonuses can you collect in $$$t$$$ seconds, if you can pass the distance 1 in one second?

Input

The first line contains two integers $$$n$$$ and $$$t$$$ ($$$1 \le n \le 200000, 0 \le t \le 10^9$$$) — the number of bonuses and the time limit.

The second line contains $$$n$$$ integers $$$x_1$$$, $$$x_2$$$,..., $$$x_n$$$ ($$$-10^9 \le x_i \le 10^9$$$) — the coordinates of the bonuses. They are sorted in increasing order ($$$x_1 \lt x_2 \lt \ldots \lt x_n$$$).

Output

Output one integer — the maximum number of bonuses that can be collected in $$$t$$$ seconds.

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

To collect 3 bonuses in $$$t = 6$$$ seconds, you must first collect the bonus with the coordinate -1, then the bonus with the coordinate 2, and in the end — the bonus with the coordinate 3. It will take you 5 seconds (1 second to collect the bonus with the coordinate -1, and 4 seconds to go from -1 to 3).

It is impossible to come to the bonus with the coordinate 7 in time. And if you first go to the bonus with the coordinate -4, you can collect only two bonuses (-4 and -1).

C. Manhattan Distance
time limit per test
5 s
memory limit per test
256 megabytes
input
standard input
output
standard output

Manhattan distance between two points $$$(x_1, y_1)$$$ and $$$(x_2, y_2)$$$ is defined as $$$|x_1 - x_2| + |y_1 - y_2|$$$.

There are $$$n$$$ pairwise distinct points on a plane. Consider all unordered pairs of these points, there are $$$\frac{n\left(n-1\right)}{2}$$$ such pairs in total. For every pair of points it is possible to calculate Manhattan distance between them. We don't ask you to calculate all such distances. Just output the $$$k$$$-th of them in increasing order.

Input

The first line contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 100000, 1 \le k \le \frac{n\left(n-1\right)}{2}$$$) — the number of points and the sequence number of the distance you have to output.

Each of the next $$$n$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$-10^8 \le x_i, y_i \le 10^8$$$) — the coordinates of the points. It is guaranteed that all $$$n$$$ points are pairwise distinct.

Output

Output the $$$k$$$-th Manhattan distance in increasing order among all unordered pairs of points.

Examples
Input
4 3
0 0
3 0
0 2
2 3
Output
3
Input
4 4
0 0
3 0
0 2
2 3
Output
4
Input
4 5
0 0
3 0
0 2
2 3
Output
5

D. Lexicographically Minimal Shortest Path
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a connected undirected unweighted graph with $$$n$$$ vertices and $$$m$$$ edges. The graph does not contain self-loops and parallel edges. Additionally, on each edge $$$(u_i, v_i)$$$ the letter $$$c_i$$$ is written.

You have to find the shortest path from the vertex 1 to the vertex $$$n$$$, and if there are several such paths, to find the one which has the string formed by the letters of this path to be lexicographically minimal.

Input

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 200000, 1 \le m \le 200000$$$) — the number of vertices and the number of edges in the graph.

Each of the next $$$m$$$ lines contains two integers $$$u_i$$$, $$$v_i$$$ ($$$1 \le u_i, v_i \le n, u_i \ne v_i$$$) — the vertices connected by the $$$i$$$-th edge, and the lowercase Latin letter $$$c_i$$$ written on this edge.

Output

In the first line output the integer $$$k$$$ — the length of the shortest path from the vertex 1 to the vertex $$$n$$$.

In the second line output $$$(k+1)$$$ integers — the sequence of vertices in the shortest path.

In the third line output the string with $$$k$$$ characters — the sequence of letters on this path. This string must be lexicographically minimal among all strings formed by shortest paths from vertex 1 to vertex $$$n$$$.

If there are several possible answers, output any of them.

Examples
Input
3 2
1 2 a
2 3 b
Output
2
1 2 3 
ab
Input
3 3
1 3 z
1 2 a
2 3 b
Output
1
1 3 
z
Input
4 4
1 2 b
2 4 a
1 3 a
3 4 z
Output
2
1 3 4 
az

E. Fluctuations of Mana
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

A mage is going to visit $$$n$$$ magical sources in fixed order. It is known that after visiting the $$$i$$$-th source the mana is changed by $$$a_i$$$ (this number can be positive, negative or zero). If the mage's mana becomes negative, he dies. What minimal amount of mana should the mage have in the beginning of his journey to successfully visit all $$$n$$$ sources and stay alive?

Input

The first line contains an integer $$$n$$$ ($$$1 \le n \le 500000$$$) — the number of magical sources.

The second line contains $$$n$$$ integers $$$a_i$$$ ($$$-10^9 \le a_i \le 10^9$$$) — the mana change after visiting the $$$i$$$-th source.

Output

Output one integer — the minimal amount of mana the mage should have to successfully complete his journey.

Example
Input
6
3 -4 2 -3 -2 7
Output
4

F. Moving Target
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are at the shooting range. There are $$$n$$$ windows in front of you, placed in a line from left to right (the leftmost window has number 1, and the rightmost window — number $$$n$$$). There is a target behind one of the windows. The exact location of the target is unknown, and there is no way to determine it. When you shoot in one of the windows, you win if you hit the target, and if you don't, the target, if it is not already behind the rightmost window, moves one window right.

You have to create a strategy that allows to hit a target in a minimal number of shots.

Input

The input contains one integer $$$n$$$ ($$$1 \le n \le 1000$$$) — the number of windows.

Output

In the first line output the integer $$$k$$$ ($$$1 \le k \le n$$$) — the minimal number of shots to hit the target for sure.

In the second line output $$$k$$$ integers $$$a_i$$$ ($$$1 \le a_i \le n$$$) — the sequence of window numbers to shot at.

Note that, as you immediately win after hitting the target, there exists a deterministic strategy that allows you to win in a minimal number of shots.

If there are several possible answers, output any of them.

Examples
Input
2
Output
2
1 2
Input
3
Output
2
1 3

G. Nuts and Bolts
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Steven has $$$n$$$ nuts and $$$n$$$ bolts. All nuts have different sizes from 1 to $$$n$$$, and all bolts have different sizes from 1 to $$$n$$$.

The operation Steven can perform is to try to compare one of the nuts with one of the bolts. As a result he will learn if the size of nut is greater, the size of bolt is greater or these nut and bolt match. He wants to find the matching nut for every bolt.

You must help Steven to do the plan, using no more than $$$5 n \log_{2}n$$$ operations.

Interaction

This is an interactive problem. Your program should communicate with the jury's program, using standard input and output for that.

At the beginning your program receives the integer $$$n$$$ ($$$2 \le n \le 1000$$$) — the number of nuts and bolts.

After that you can make no more than $$$5 n \log_{2}n$$$ queries. To do a query, output the character "?", and then numbers $$$i$$$ and $$$j$$$ ($$$1 \le i \le n, 1 \le j \le n$$$) — the number of nut and the number of bolt that Steven will try to compare.

As a result, you receive one of the three characters:

  • "<", if the size of the $$$i$$$-th nut is less than the size of the $$$j$$$-th bolt,
  • "=", if the $$$i$$$-th nut and the $$$j$$$-th bolt match,
  • ">", if the size of the $$$i$$$-th nut is greater than the size of the $$$j$$$-th bolt.

As soon as you can say which nut matches which bolt, output the character "!", and then $$$n$$$ distinct integers $$$p_i$$$ ($$$1 \le p_i \le n$$$), where $$$p_i$$$ is the number of bolt which matches the nut with the number $$$i$$$. After that your program must terminate.

Example
Input
5

<

<

>

>

<

=

=

=

=

=
Output

? 1 1

? 2 2

? 3 3

? 4 4

? 5 5

? 1 4

? 2 3

? 3 2

? 4 5

? 5 1

! 4 3 2 5 1
Note

Please note that each your message must end with a line break. Also after outputting each message your program must flush the stream buffer, so that the outputted information could reach jury's program: for instance, this can be done by calling "fflush(stdout)" or "cout.flush()" in C++, "System.out.flush()" in Java, "Console.Out.Flush()" in C#, "flush(output)" in Pascal, "sys.stdout.flush()" in Python.

Emply lines in the sample are given only for convenience, to make it clear in which order the messages are written. When solving the problem you must not output empty lines and jury's program won't output empty lines too.

H. Tree Painting
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a tree with $$$n$$$ vertices and $$$(n-1)$$$ edges. At the beginning its edges and vertices are not painted. You can perform the following operation: choose two vertices in the tree and paint the path between them (all vertices and edges along this path are painted).

What is the minimal number of such operations to paint the whole tree (all edges and all vertices)?

Input

The first line contains the integer $$$n$$$ ($$$2 \le n \le 200000$$$) — the number of vertices in the tree.

Each of the next $$$(n-1)$$$ lines contains two integers $$$u_i$$$, $$$v_i$$$ ($$$1 \le u_i, v_i \le n, u_i \ne v_i$$$) — the vertices connected by the $$$i$$$-th edge.

Output

Output one integer — the minimal number of operations to paint the tree.

Examples
Input
5
1 2
1 3
1 4
1 5
Output
2
Input
5
1 2
2 3
3 4
4 5
Output
1
Input
4
1 2
3 2
4 2
Output
2

I. Sorting Colored Array
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given the array of $$$n$$$ integers. Each number in the array is colored. In one operation you can swap two adjacent differently colored elements. Is it possible to sort the array with some number of such operations?

Input

The first line contains the integer $$$n$$$ ($$$1 \le n \le 200000$$$) — the size of the array.

Each of the next $$$n$$$ lines contains two integers $$$a_i$$$, $$$c_i$$$ ($$$-10^9 \le a_i \le 10^9, 1 \le c_i \le 200000$$$) — the value of the $$$i$$$-th element of the array and its color.

Output

Output "YES" or "NO", depending on is it possible to sort the array using the given operation or not.

Examples
Input
6
1 2
-1 3
-3 1
3 2
0 1
2 3
Output
YES
Input
6
1 2
-1 1
-3 1
3 2
0 3
2 3
Output
NO
Note

In the first test the following sequence of operations sorts the array:

1) swap (1, 2) and (-1, 3)

2) swap (1, 2) and (-3, 1)

3) swap (-1, 3) and (-3, 1)

4) swap (3, 2) and (0, 1)

5) swap (1, 2) and (0, 1)

6) swap (3, 2) and (2, 3)

The resulting array will be:

-3 1

-1 3

0 1

1 2

2 3

3 2

In the second test the elements (-1, 1) and (-3, 1) must be swapped to sort the array, but such swap is prohibited.

J. The Battle of Mages
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Two mages play the game. Both of them has their own set of creatures. Each creature is characterized by the integer — its strength. At the beginning of the game each mage summons $$$k$$$ distinct random creatures from their set of creatures, and each subset of $$$k$$$ creatures can be summoned equally likely. The mage who has the greater sum of strengths of their creatures wins. If the sums of strength are equal, the process repeats. If every subset of creatures of both mages always has the same strength, the draw is declared.

It has turned out, that if $$$k=1$$$ or $$$k=3$$$, the first mage has strictly greater chances to win, and if $$$k=2$$$, the second mage has. You have to give an example of sets of creatures of the first and the second mages.

Input

This problem has only one test, and it is empty.

Output

In the first line output one integer $$$n_1$$$ ($$$3 \le n_1 \le 10$$$) — the number of creatures in the first mage's set.

In the second line output $$$n_1$$$ integers $$$s_{1i}$$$ ($$$1 \le s_{1i} \le 10$$$) — the strengths of creatures of the first mage.

In the third line output one integer $$$n_2$$$ ($$$3 \le n_2 \le 10$$$) — the number of creatures in the second mage's set.

In the fourth line output $$$n_2$$$ integers $$$s_{2i}$$$ ($$$1 \le s_{2i} \le 10$$$) — the strengths of creatures of the second mage.

If there are several possible answers, output any of them. It is guaranteed that the solution in the given constraints exists.

Example
Input
Output
3
1 2 3
3
2 2 2

Note
The output example is not an answer for the problem and is given only for better understanding of output format and to clarify the problem statement.
The first mage has three creatures, their strengths are 1, 2 and 3. The second mage has three creatures, all their strengths are equal to 2.
If $$$k = 1$$$, the second mage always has fixed strength 2. If the first mage summons the creature with the strength 2, the process repeats. If he summons the creature with the strength 3, he wins, and with the strength 1 — loses. The probability of the first mage to win is 0.5, but the problem requires the first mage to have strictly better chances.
If $$$k = 2$$$, the second mage always has strength 4. The first mage can summon the following subsets of creatures: (1, 2), (1, 3), (2, 3). If it is (1, 2), the first mage loses (as 3 < 4), if it is (1, 3) — the game starts again (as 4 = 4), and if it's (2, 3) — he wins. The resulting probability is again 0.5, but the second mage should have better chances in this case.
If $$$k = 3$$$, the subsets of the first and second mages are always (1, 2, 3) and (2, 2, 2). They have equal strengths, and we got infinite game restarts. According to the rules, the draw is declared in this case, so the probability of the first mage winning is not greater again.
  







        

        





    
        
K. Table
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
There are 4 bars, possibly, having different lengths. Can they be used as the legs of the table, such that:
     
  •  The legs stay vertically in the vertices of some rectangle; 
  •  The surface of the table, possibly, sloping, touches all four legs? 
Input
The input contains 4 integers $$$a_1$$$, $$$a_2$$$, $$$a_3$$$, $$$a_4$$$ ($$$1 \le a_i \le 10^9$$$) — the lengths of the bars.
Output
Output "YES" or "NO", depending on it is possible to make a table with the given design or not.
Examples
Input
1 1 1 1

Output
YES

Input
1 5 1 5

Output
YES

Input
1 3 2 2

Output
YES

Input
9 5 11 8

Output
NO

  







        

        





    
        
L. The Dragon Land
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
A hero is going to make a journey through the dragon land. The dragon land is a road, and $$$n$$$ dragon lairs are situated along this road. The hero will follow this road, never turning back.
Passing by the dragon lair, it is possible to fight the dragon, kill him and get $$$a_i$$$ gold. But it is not always profitable to kill all the dragons, as the weapons and armor wear out: after the first battle the hero will have to spend 1 gold on repairing them, after the second battle — 2 gold, and so on, after the $$$k$$$-th battle he will have to spend $$$k$$$ gold.
Initially the hero has no gold. At any moment of his journey and after it the hero can't have negative amount of gold.
How much gold the hero can earn in the journey?
Input
The first line contains the integer $$$n$$$ ($$$1 \le n \le 200000$$$) — the number of dragon lairs.
The second line contains $$$n$$$ integers $$$a_i$$$ ($$$1 \le a_i \le 10^9$$$) — amounts of gold the hero can earn fighting the $$$i$$$-th dragon.
Output
Output one integer — the maximal hero's profit.
Examples
Input
5
8 2 4 9 1

Output
15

Input
2
1 1

Output
0

  







        

        





    
        
M. Notifications
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Vasya is sitting at a computer. Sometimes he receives notifications about new videos on his favourite Youtube channel. Then,
     
  •  if he isn't watching any video at the moment, he clicks the notification and starts to watch this video till the end, 
  •  if he is already watching a video at the moment, he will firstly watch all unfinished videos (about which he received notification earlier), and then click the new notification and watch the new video till the end. 
You are given $$$n$$$ parameters of the notifications: the $$$i$$$-th notification is received at the moment of time $$$t_i$$$ and contains the video of length $$$d_i$$$. Find when Vasya will stop watching the last video.
Input
The first line contains the integer $$$n$$$ ($$$1 \le n \le 200000$$$) — the number of notifications.
Each of the next $$$n$$$ lines contains two integers $$$t_i$$$ and $$$d_i$$$ ($$$1 \le t_i, d_i \le 10^9$$$) — the moment of time when Vasya receives the $$$i$$$-th notification, and the length of the video in this notification.
All $$$t_i$$$ form non-decreasing sequence, i. e. $$$t_i \le t_{i+1}$$$ for all $$$i$$$ from 1 to $$$(n-1)$$$.
Output
Output one integer — the moment of time when Vasya will stop watching the last video.
Example
Input
5
1 4
3 3
6 1
10 2
10 3

Output
15

Note
In the given example the sequence of Vasya's actions is the following:
1) At the moment 1 he receives a notification about the video of length 4. As he isn't watching any video at the moment, he starts to watch it till the moment of time 5.
2) At the moment 3 he receives a notification about the video of length 3, but he is watching the first video at the moment, so he will start watching this video at the moment 5 (just after the first one) and finish at the moment 8.
3) At the moment 6 he receives a notification about the video of length 1. He will watch it from the moment 8 to the moment 9.
4) From the moment 9 to the moment 10, Vasya is not doing anything.
5) At the moment 10 he receives two notification — about the videos of lengths 2 and 3. He will watch them in the order he receives them, so he will watch the first of them from 10 to 12, and the other one — from 12 to 15.