2016, Samara University ACM ICPC Quarterfinal Qualification Contest
A. Balls in Urn
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Sergey takes part in a TV show «Battle of Prophets», in another episode of which the task of the participants is guessing the colors of the balls taken by the show host out of the opaque urn. Using a spirit ritual he found out that the urn contains balls of n different colors, and the number of balls of the i-th color is exactly ai. The show host is planning to take out balls one by one until the urn becomes empty, and Sergey will have to say the ball's color every time before it is taken out. Unfortunately, the ancient spirits refuse to help him, and he has to trust his intuition only. Sergey wants to guess the color of as many balls as possible in the worst case and is now thinking how many times he is able to make a correct guess for sure.

Input

The first line contains a single integer n (1 ≤ n ≤ 2·105) — the number of different colors.

The second line contains n space-separated integers: ai (1 ≤ ai ≤ 109) — the number of balls of the i-th color in the urn.

Output

Output a single integer — the maximal number of balls whose color Sergey can definitely guess.

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

B. No Time for Dragons
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

One fairy king hated dragons to death. Not only that these monsters burn whole villages to ashes, kidnap princesses and guard treasures that they don't need at all, but they are also mentioned in statements of programming problems very often. To end their tyranny, he decided to recruit an army and destroy these damned creatures once and forever.

The king found out that there are n dragons in total, and to defeat the i-th of them he needs an army of ai soldiers, bi of which will be killed during the battle. Now he wants to know the minimal number of soldiers he needs to recruit in order to kill all the dragons. The king doesn't care about the order of battles: the only thing that matters is that none of the dragons will be left alive.

Input

The first line contains a single integer n (1 ≤ n ≤ 2·105) — the number of dragons.

Each of the next n lines contains two space-separated integers: ai and bi (1 ≤ bi ≤ ai ≤ 109) — the number of soldiers needed to defeat the i-th dragon, and the number of soldiers that will be killed in the battle against him.

Output

Output a single integer — the minimal number of soldiers that is sufficient to kill all the dragons.

Examples
Input
2
7 4
5 1
Output
8
Input
3
4 1
6 4
5 3
Output
10

C. Mathematical Field of Experiments
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Mathematician Michael is dreaming how he becomes a Minister of Education in Russia and tries his innovative experimental educational program in Maths in an elementary school. The main feature of this program is learning arithmetical operations in fields of integers modulo prime numbers instead of fields of real numbers. Impressed by his idea, Michael has started to write a Maths textbook for the 1st grade kids and is already preparing exercises to find a square root in modular arithmetic.

In each such exercise an integer x is given, and it's needed to find its square root modulo prime number p, which is also given. The correct answer for such task is an integer s, such that s·s and x have the same remainder after division by p. In other words, the number has to leave no remainder after division by p. It must be said that the square root s doesn't exist for some numbers x.

To speedup the process of preparing tasks in this topic, Michael decided to write a program that finds square roots modulo given prime number p for all numbers x from 0 to , or tells that the corresponding square root doesn't exist.

Input

The first line contains a prime number p (2 ≤ p ≤ 106). A prime number has exactly two different divisors.

Output

Output p space-separated integers, the i-th of which must be equal to the square root of modulo p. All numbers must be between 0 and . If some square root doesn't exist, output  - 1 instead of it, and if there are multiple square roots for some i, output any of them.

Examples
Input
5
Output
0 4 -1 -1 3
Input
7
Output
0 1 3 -1 5 -1 -1
Note

In the first sample: , .

D. Behind the Wall
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Space marine officer Sarah and her small squad appeared to be on a hostile planet full of species of zorcs, an alien race known for their radical extremist views to other species. Fighting against zorcs would be a great disrespect to their rich culture so she wants to cover her base with a wall as soon as possible and then safely wait for the reinforcements promised by the command center.

The map of the temporarily safe area is a cell field of n rows, each consisting of m cells. The base is located in the c-th cell of the r-th row. Sarah has estimated that building a wall in the j-th cell of the i-th row takes ai, j units of time. She thinks that zorcs cannot pass through the cell where a wall is built. It's required to build walls in such a way that zorcs can't reach the base from outside the cell field, moving only through cells that have a common side and that doesn't have a wall built on them. The walls must be built in a minimal possible time, taking into account that they are build consequently one after another, and no time passes between building walls in different cells. Of course, it's prohibited to build a wall in a cell with the base.

Sarah is wondering in which cells walls must be built. Luckily, she has a programmer in her squad who started to solve this task.

Input

The first line contains four space-separated integers: n, m, r and c (3 ≤ n, m ≤ 50, 2 ≤ r ≤ n - 1, 2 ≤ c ≤ m - 1) — the height and width of the field, and the numbers of row and column where the base is located. Each of the next n lines contains m integers: ai, j (0 ≤ ai, j ≤ 500) — the number of time units needed to build a wall in the cell in the i-th row and the j-th column. It's guaranteed that ar, c = 0.

Output

In the first line output a single integer — the minimal number of time units required to build the walls.

Then output n lines of m characters each. In the i-th line, on the j-th position output «.», if the wall must not be built in this cell, or «X», if the wall must be built in this cell. If there are several correct building plans, output any of them.

Examples
Input
3 4 2 2
9 1 1 9
1 0 9 1
9 1 1 9
Output
6
.XX.
X..X
.XX.
Input
3 3 2 2
1 0 1
9 0 6
1 8 1
Output
23
.X.
X.X
.X.

E. The Best among Equals
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

A university in Samara has held a qualification contest in figure programming, but the jury can't come to terms how many teams should take part in the next stage of the contest. In figure programming a judge system doesn't evaluate the scores precisely and just set an interval which the score can belong to. Jury is able to evaluate any participant with any score from this interval. There are n teams that took part in the contest, and the i-th of them has the score in the interval from li to ri, inclusively. Jury wants the number of qualified teams to be as large as possible, but they have to get the maximal score among all teams. What is the maximal number of teams that can take part in the next stage of the contest under such circumstances?

Input

The first line contains a single integer n (1 ≤ n ≤ 2·105) — the number of teams in the contest.

Each of the next n lines contains two space-separated integers: li and ri ( - 109 ≤ li ≤ ri ≤  + 109) — the lower and upper bounds of the score for the i-th team.

Output

Output a single integer — the maximal number of teams that can get the maximal score.

Example
Input
3
1 3
2 4
4 5
Output
2

F. The Weakest Sith
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In a galaxy far, far away the great galactic empire had collapsed after the death of the emperor, and now a new corrupted galactic republic gradually grows stronger. But the evil Sith don't spend time in vain: they've created opposition named «The last order» and now they are planning to choose a leader by a fair tournament.

In the tournament there will be n Siths who has left alive. The i-th of these Siths has three integer characteristics: mastery of lightsabers ai, mastery of the Force bi and the level of mental balance ci. All characteristics of all Siths are different. The tournament consists of one on one fights. The winner of each of these fights is the Sith who has at least two characteristics that are bigger than their opponent's corresponding ones.

The problem is that the Sith tournaments have never been organized to find the strongest Sith who could beat anyone else: instead, they were supposed to distinguish the weakest one, somebody who couldn't win any fight, and to let everybody take a good laugh at that loser. It seems like such Sith will become the leader of «The last order», so it'd be good to know them in advance.

Input

The first line contains a single integer n (2 ≤ n ≤ 2·105) — the number of the Siths who will participate in the tournament.

Each of the next n lines contains three space-separated integers: ai, bi, ci (1 ≤ ai, bi, ci ≤ 109) — the three corresponding characteristics of the i-th Sith.

Output

In the first line output a single integer — the number of Siths who can't win any fight.

In the second line print the numbers of those Siths separated by a space.

Examples
Input
4
3 11 9
1 4 8
5 2 10
12 7 6
Output
1
2
Input
3
700 40 1
50 2 800
3 900 60
Output
0

G. Of Zorcs and Axes
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Zorcs don't like other species. Zorcs like massive curve axes. Right now each of them is going to choose a suitable axe and show beings of other races entrenched nearby that they are not ready to peaceful cultural assimilation. There are n zorcs and m axes in total, and the i-th zorc wants to take an axe with the weight not less than ai and the curvature not less than bi, while the j-th axe has the weight wj and the curvature cj. Zorcs don't like programming problems. Zorcs like massive curve axes. So it's your task to determine which zorc must choose which axe.

Input

The first line contains a single integer n (1 ≤ n ≤ 2·105) — the number of zorcs.

Each of the next n lines contains two space-separated integers: ai and bi (1 ≤ ai, bi ≤ 109) — the minimal weight and curvature of the axe that suits the i-th zorc.

The next line contains a single integer m (1 ≤ m ≤ 2·105) — the number of axes.

Each of the next m lines contains two space-separated integers: wj and cj (1 ≤ wj, cj ≤ 109) — the weight and the curvature of the j-th axe.

Output

Output n integers, the i-th of which must be the number of axe that should be given to the i-th zorc to fulfill all his requirements. Of course, the same axe can't be given to two different zorcs.

If there is no possibility to distribute axes, fulfilling all requirements of all zorcs, output a single number  - 1 instead of that.

Examples
Input
3
3 4
5 1
2 6
4
5 7
4 5
3 3
5 2
Output
2 4 1
Input
2
2 5
4 3
2
5 6
3 4
Output
-1

H. Streets of Working Lanterns
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Policeman Anatoliy monitors a lair of unorganized criminal group spreading prohibited Asian drawings. The lair has only one entrance, which is also an exit. When someone enters into the lair, Anatoliy writes an opening round bracket in his notepad, and when someone comes out, he writes a closing round bracket.

Long surveillance provokes an appetite, so Anatoliy has to eat donuts not to starve to death. Unfortunately, after the surveillance had ended, Anatoliy discovered a lot of greasy stains left by donuts in his notepad, and they prevent to understand which brackets are opening or closing. He doesn't want his boss to shout on him, so he must restore his records. He ensured that the lair of criminals was empty before he started the surveillance and after he ended it.

Input

The input contains a single string of length no more than 5·105. This string consists of characters «(», «)» and «?». Character «(» means that someone entered into the lair, character «)» means that someone came out of it, and character «?» means that there is a greasy stain on this place, and it's impossible to determine which of the other two characters was there initially.

Output

Output a recovered string consisting of characters «(» and «)» only, so that Anatoliy really could write it in his notepad. If there are many suitable strings, output any of them. If Anatoliy messed up something and his records contained mistakes, output «Impossible», without quotes.

Examples
Input
(?(?))
Output
()(())
Input
()
Output
()
Input
?(
Output
Impossible

I. It's the Police
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Yuriy is a corrupted head of police. Every day he has to set policemen to the posts in the city so that local gangs still could commit crimes. The city has n squares connected by m streets so that the j-th street connects the aj-th and the bj-th squares. A policeman, being set on some square, can observe this square and also all squares connected with it. Yuriy wants to set policemen in such a way that at least one square is not observed, which lets the gangs to do their dark business on this square. Of course, Yuriy doesn't want to be suspicious, so he plans to set policemen to as many squares as possible.

Input

The first line contains two space-separated integers: n and m (1 ≤ n ≤ 2·105, 0 ≤ m ≤ 2·105) — the numbers of squares and streets in the city.

Each of the next m lines contains two space-separated integers: aj and bj (1 ≤ aj, bj ≤ n, aj ≠ bj) — the numbers of squares connected by the j-th street. Every pair of squares can be connected by at most one street.

Output

Output n space-separated integers. On the i-th position output 1, if a policeman should be set to the i-th square, or 0 if it shouldn't be done. If there are many possible solutions, output any of them.

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

J. Panoramic Photography
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Most of the students of the law school prefer visiting photo club to the competitions in Roman law. Members of the photo club visit different interesting places, take photos of each other in front of them, and then rate their photos.

Once they appeared on a unbelievably long street which had n buildings in a row. Every member of the photo club took a photo contained, besides the members of the club and people passing by, a segment of the street. In other words, if you number the buildings in the order they are located on the street, each photo contained some buildings with the consecutive numbers.

Some day a Roman law professor of that law school came across the exhibition of the photos from that street. He hasn't remembered how many photos were there, but he has noticed that the i-th building was captured on ai photos. Now he wants to estimate the minimal number of his students in the photo club, considering that no one could present more that one photo at the exhibition.

Input

The first line contains a single integer n (1 ≤ n ≤ 2·105) — the number of buildings.

The second line contains n space-separated integers: ai (0 ≤ ai ≤ 109) — the number of photos that contain the i-th building.

Output

Output a single integer — the minimal number of students in the photo club.

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

K. Revenge of the Dragon
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

One fairy king hated dragons to death. He gathered a big army and killed every single one of them. But he overlooked a small dragon egg, thinking it was a stone, and the last dragon hatched from this egg soon. Quickly determined who is responsible of the genocide of dragons, the last dragon got angry and destroyed all the kingdom. There was no army to defend from him as it was all spent to annihilate other dragons.

A fairy kingdom is a coordinate plane. The king with the remains of his army took shelter in a palace located in the point . The palace is securely defended, and the dragon can't destroy it. Realized that, the dragon hid in the point , hoping to attack the king when he comes out of the palace. The king soon learned where the dragon is hiding and tries to estimate the danger of the situation.

If the king is out of the palace, the dragon can notice it at any moment and fly towards him from his lair. It will be spotted by the king's guards immediately, and the king will immediately move straight to the palace, uniformly, until he gets safe behind its walls. The dragon is looking for revenge, so every moment of time he uniformly moves straight to the current king's location. The king is quite old, while the dragon is full of strength, so the speed of the king is twice slower than the speed of the dragon. The king wants to estimate to what extent the dragon infringes the freedom of his movements, so he would like to know the area of the safe part of the plane, where he can walk without fears that the dragon can catch him earlier than he reaches the palace.

Input

The first line contains two space-separated integers: xp and yp ( - 1000 ≤ xp, yp ≤  + 1000) — the coordinates of the palace.

The second line contains two space-separated integers: xd and yd ( - 1000 ≤ xd, yd ≤  + 1000) — the coordinates of the dragon's lair.

These two points don't coincide.

Output

Output a single floating-point number — the area of the safe part of the plane. The absolute of relative error must not exceed 10 - 6.

Example
Input
0 0
1 0
Output
0.916297857297023

L. Right Build
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In a MMORPG «Path of Exile» characters grow by acquiring talents for special talent points received in a game process. Talents can depend on others. A talent can be acquired only if a character has at least one of the talents it depends on. Acquiring one talent costs one talent point. At the beginning of the game a character has a single starting talent.

Schoolboy Vasiliy decided to record a video manual how to level-up a character in a proper way, following which makes defeating other players and NPCs very easy. He numbered all talents as integers from 0 to n, so that the starting talent is numbered as 0. Vasiliy thinks that the only right build is acquiring two different talents a and b as quickly as possible because these talents are imbalanced and much stronger than any others. Vasiliy is lost in thought what minimal number of talent points is sufficient to acquire these talents from the start of the game.

Input

The first line contains four space-separated integers: n, m, a and b (2 ≤ n, m ≤ 2·105, 1 ≤ a, b ≤ n, a ≠ b) — the total number of talents, excluding the starting talent, the number of dependencies between talents, and the numbers of talents that must be acquired.

Each of the next m lines contains two space-separated integers: xj and yj (0 ≤ xj ≤ n, 1 ≤ yj ≤ n, xj ≠ yj), which means the talent yj depends on the talent xj. It's guaranteed that it's possible to acquire all talents given the infinite number of talent points.

Output

Output a single integer — the minimal number of talent points sufficient to acquire talents a and b.

Examples
Input
6 8 4 6
0 1
0 2
1 2
1 5
2 3
2 4
3 6
5 6
Output
4
Input
4 6 3 4
0 1
0 2
1 3
2 4
3 4
4 3
Output
3

M. Ex Machina
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Special agent Adam is hacking a calculator of a member of the secret mason organization of Illuminati in order to get access to the information about its leaders. He has already found out that the organization consists of n members, each of which has its own unique index number from 1 to n. Moreover, every member of the organization has a level which is also an integer from 1 to n, and all levels are pairwise distinct. Every Illuminati can give commands to Illuminati of lower levels, but has to obey the Illuminati of higher levels. Adam thinks that the information leak about the Illuminati with the highest level n can discredit him, so he is interested in the Illuminati with the level n - 1, who obeys only the Illuminati with the highest level.

It was quite hard to get access to the secret Illuminati network, so the only request Adam can make is to compare levels of two Illuminati with the given index numbers. Making such request, he gets a response which tells if the level of the first Illuminati is higher, lower or equal to the level of the second Illuminati. The number of requests is limited, but as the Illuminati's calculator highly respects powers of two, Adam can safely make requests before his presence in the network will be detected.

Interaction

It's an interactive problem. Here, your program must communicate with the jury's program using standard input and output.

At the beginning, the input contains a line with a single integer n (2 ≤ n ≤ 1000) — the number of Illuminati.

After that your program can make requests to compare two Illuminati. To do that, in a separate line output a character «?» and then two integers, separated by spaces — the index numbers of Illuminati to compare. As a response, a separate line will contain a character «<» if the first Illuminati has the level lower than the second one, a character «>» if the first Illuminati has the level higher than the second one, or a character «=» if the given Illuminati have the same level. You can make no more than such requests.

When you will know the answer, output a character «!» and a single integer, separated by a space — the index number of Illuminati with the level n - 1.

Example
Input
5
>
>
>
>
>
<
>
Output
? 1 2
? 1 3
? 1 4
? 1 5
? 2 3
? 2 4
? 4 5
! 4
Note

Notice that after printing each message your program must flush the output buffer so that the information you have printed reached the jury's program. For example, the calls «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 do that.