2019, XII Samara Regional Intercollegiate Programming Contest
A. Rooms and Passages
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$(n+1)$$$ rooms in the dungeon, consequently connected by $$$n$$$ passages. The rooms are numbered from $$$0$$$ to $$$n$$$, and the passages — from $$$1$$$ to $$$n$$$. The $$$i$$$-th passage connects rooms $$$(i-1)$$$ and $$$i$$$.

Every passage is equipped with a security device of one of two types. Security device of the first type checks if a person who walks through the passage has the pass of the certain color, and forbids movement if such pass is invalid. Security device of the second type never forbids movement, but the pass of the certain color becomes invalid after the person walks through.

In the beginning you are located in the room $$$s$$$ and have all the passes. For every $$$s$$$ from $$$0$$$ to $$$(n-1)$$$ find how many rooms you can walk through in the direction of the room $$$n$$$.

Input

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

The second line contains $$$n$$$ integers $$$a_i$$$ ($$$1 \le |a_i| \le n$$$). The number $$$|a_i|$$$ is a color of the pass which the $$$i$$$-th passage works with. If $$$a_i \gt 0$$$, the $$$i$$$-th passage is the first type passage, and if $$$a_i \lt 0$$$ — the second type.

Output

Output $$$n$$$ integers: answers for every $$$s$$$ from $$$0$$$ to $$$(n-1)$$$.

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

B. Rearrange Columns
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There is a cell field of size $$$2 \times n$$$. Some cells are marked. You have to rearrange its columns in such a way that all marked cells form a connected area.

Marked cells form a connected area if from every one of them it is possible to reach every other one, moving up, down, left or right (not always in one direction), and all the cells on the way are marked too.

Input

The input describes a field and consists of two strings of the same length $$$n$$$ ($$$1 \le n \le 1000$$$). They consist of characters «.» and «#» that denote not marked and marked cells, respectively. It is guaranteed that there exists at least one marked cell.

Output

In the first line output «YES» or «NO», depending on if the columns can be rearranged or not.

In case of the positive answer output two strings of characters «.» and «#» — the field after the columns are rearranged.

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

Examples
Input
#..#
.#.#
Output
YES
##..
.##.
Input
..##
##..
Output
NO

C. Jumps on a Circle
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There are p points on the circle numbered from 0 to (p - 1) in a way that from the point 0 you can move to the point 1, from the point 1 — to the point 2, and so on, and from the point (p - 1) you can move to the point 0.

A chip is initially placed at the point 0. It starts to jump around the circle, first moving 1 point forward, then 2 points forward, then 3 points forward and so on.

How many unique points (including the start one) will be visited by a chip after n moves?

Input

The input has two integers p and n (1 ≤ p ≤ 107, 0 ≤ n ≤ 1018) — the number of points on a circle and the number of moves.

Output

Output a single integer — the number of unique points visited by a chip.

Examples
Input
3 10
Output
2
Input
5 3
Output
3
Input
8 1000000000000000000
Output
8
D. Country Division
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

A country has $$$n$$$ cities that are connected by $$$(n-1)$$$ roads, and it is possible to reach every city from every other city. Before the election political analysts have made $$$q$$$ predictions how the election will proceed. In each of these predictions it is supposed that some cities will support one candidate (we will call such cities red), some other cities will support another candidate (we will call such cities blue), and the citizens in the remaining cities don't care about politics and they don't support anyone.

For every prediction you have to answer, is it possible or not to block some roads so that from every red city it is possible to reach every other red city, from every blue city it is possible to reach every other blue city, but from every red city it is not possible to reach every blue city.

Input

The first line contains an integer $$$n$$$ ($$$2 \le n \le 200000$$$) — the number of cities.

Each of the next $$$(n-1)$$$ lines contains two integers $$$u_i, v_i$$$ ($$$1 \le u_i, v_i \le n$$$) — the numbers of cities connected by roads.

The next line contains an integer $$$q$$$ ($$$1 \le n \le 200000$$$) — the number of predictions.

Each of the next $$$q$$$ lines contains a description of the prediction. It starts with two integers $$$r_j$$$ and $$$b_j$$$ ($$$1 \le r_j, b_j \lt n, r_j + b_j \le n$$$) — how many red and blue cities this prediction has. Then $$$r_j$$$ integers follow — the numbers of red cities. Then $$$b_j$$$ integers follow — the numbers of blue cities. All cities in each prediction are distinct.

The sum of all $$$r_j$$$ and $$$b_j$$$ over all predictions doesn't exceed $$$200000$$$.

Output

For every prediction, output the answer for it — «YES» or «NO» — in a separate line.

Example
Input
7
1 2
1 3
2 4
2 5
3 6
3 7
6
2 2 4 5 6 7
2 2 4 6 5 7
2 1 4 5 2
2 1 4 5 1
1 1 1 2
6 1 1 2 3 4 5 6 7
Output
YES
NO
NO
YES
YES
YES

E. Third-Party Software - 2
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Pavel is developing another game. To do that, he again needs functions available in a third-party library too famous to be called. There are $$$m$$$ functions numbered from $$$1$$$ to $$$m$$$, and it is known that the $$$i$$$-th version of the library contains functions from $$$a_i$$$ to $$$b_i$$$ inclusively.

The library is not free and Pavel needs all the functions. What minimal number of versions does he need to purchase to be able to use all the functions?

Input

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 200000, 1 \le m \le 10^{9}$$$) — the number of library versions and the number of functions.

Each of the next $$$n$$$ lines contains two integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \le a_i \le b_i \le m$$$) — the interval of function numbers available in the $$$i$$$-th version.

Output

In the first line output «YES» or «NO», depending on if it's possible or not to purchase library versions to use all the functions.

In case of the positive answer output two more lines. In the second line output a single integer $$$k$$$ — the minimal number of library versions needed to be purchased. In the third line output $$$k$$$ distinct integers — the numbers of versions needed to be purchased.

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

Examples
Input
4 8
1 2
3 4
5 6
7 8
Output
YES
4
1 2 3 4
Input
4 8
1 5
2 7
3 4
6 8
Output
YES
2
1 4
Input
3 8
1 3
4 5
6 7
Output
NO

F. Friendly Fire
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Nikita is a fan of Volvo Software games. Not so long ago this company has released a game too famous to be called.

Nikita's opponent has $$$n$$$ creatures, and the $$$i$$$-th of them has attack $$$a_i$$$ and has $$$h_i$$$ hit points. Nikita has a Friendly Fire spell. This spell is casted on two enemy creatures, and they simultaneously attack each other once. If the attacker's attack is greater or equal than the target's hit points, the target dies.

Help Nikita to choose two targets for Friendly Fire, so that the sum of attacks of all opponent's creatures will become as small as possible.

Input

The first line contains an integer $$$n$$$ ($$$2 \le n \le 300000$$$) — the number of the opponent's creatures.

Each of the next $$$n$$$ lines contains two integers $$$a_i$$$ and $$$h_i$$$ ($$$1 \le a_i, h_i \le 10^{9}$$$) — attack and hit points of the $$$i$$$-th creature.

Output

In the first line output a single integer — the maximal possible decrease of the total attack of the opponent's creatures.

In the second line output two distinct integers from $$$1$$$ to $$$n$$$ — the numbers of creatures to cast the spell on.

If there are many possible answers, you may output any of them.

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

G. Akinator
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

One day hacker Dmitry found an interesting game called Akinator. The rules of the game are very simple: player thinks of some famous person and Akinator tries to guess this person in a limited number of questions. Every turn Akinator asks player: «Is this person i1 or i2 or ... or im?» (here m is the number of people in the question, it can differ from question to question). The player answers «Yes» or «No», and Akinator will use obtained information. As soon as Akinator knows the thought person, he says the answer and wins. If Akinator can't guess the person in the given number of questions, he loses.

Akinator has k questions to guess the thought person. It is known in advance that Dmitry has thought of one of these n people: 1, 2, ..., n with the probabilities p1, p2, ..., pn. Determine if Akinator can guarantee his guess in k questions, and if he can, what is the minimal average number of questions he needs for that.

Input

First line contains two integers n and k (1 ≤ k ≤ n ≤ 100) — number of possibly thought persons and number of questions.

Second line contains n integers a1, a2, ... an (1 ≤ ai ≤ 1012). Probabilities pi are proportional to ai, that is, they can be calculated as .

Output

If Akinator can't surely guess the thought person, output «No solution».

Otherwise output the irreducible fraction — the minimal average number of questions Akinator needs to win the game.

Examples
Input
4 1
8 1 9 2
Output
No solution
Input
4 2
1 2 3 4
Output
2/1
Input
4 3
1 2 3 4
Output
19/10
Note

In the third sample Akinator has 3 attempts. It is optimal to ask the first question about the 4th person. If the answer «No» is received, ask about the 3rd person. If the answer «No» is received here as well, use the last question to choose between 1st and 2nd persons.

The average number of attempts here is 0.4·1 + 0.3·2 + 0.2·3 + 0.1·3 = 1.9.

H. Missing Number
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Thomas has an array of integers $$$a_1,~\ldots,~a_n$$$, and all the elements in this array are distinct and belong to the interval from $$$0$$$ to $$$n$$$. As you can see, one of the numbers from $$$0$$$ to $$$n$$$ is missing in this array.

You have to find this number. You can ask the $$$b$$$-th bit of the number $$$a_i$$$ no more than $$$2 \cdot n + 19$$$ times.

Interaction

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

In the beginning your program gets a single integer $$$n$$$ ($$$1 \le n \le 1000$$$) — the size of the array.

After that you can ask no more than $$$2 \cdot n + 19$$$ questions. To ask a question, output a character «?», and then after a space two integers $$$i$$$ and $$$b$$$ ($$$1 \le i \le n, 0 \le b \le \log_{2}n$$$) — the index $$$i$$$ in the array and the bit you want to know. Bits are numbered from zero, starting from the lowest.

As a response you will get an integer $$$0$$$ or $$$1$$$ — the value of the $$$b$$$-th bit of the number $$$a_i$$$.

When you determine the number missing in the array, output a character «!», and then after a space output this number. Then your program must terminate.

Example
Input
3

0

1

0
Output

? 1 1

? 2 0

? 3 1

! 2
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.

I. Painting a Square
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There is a square of size $$$a \times a$$$. In its top left corner there is a square brush of size $$$b \times b$$$. You should use this brush to paint a square (you can assume that the top left corner of size $$$b \times b$$$ is already painted). It is allowed to move a brush only in parallel to the square's sides. What is the minimal distance the center of the brush should pass to make the whole square painted?

Input

The input contains two integers $$$a$$$ and $$$b$$$ ($$$1 \le b \le a \le 10^{6}$$$) — the sides of the square and the brush, correspondingly.

Output

Output a single integer — the minimal distance that should be passed by the center of the brush. It is guaranteed that the answer is an integer.

Examples
Input
4 2
Output
6
Input
4 3
Output
3
Input
9 3
Output
24
Input
1000000 1
Output
999999999999

J. The Power of the Dark Side - 2
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

On the Jedi Tournament $$$n$$$ Jedi are battling each other. Every Jedi has three parameters: strength, agility and intelligence. When two Jedi have a fight, the winner will be the Jedi which has at least two parameters higher compared to the same parameters of his opponent. For example, Jedi with parameters (5, 9, 10) defeats Jedi with parameters (2, 12, 4) because of first and third parameters.

Sith have a plan to turn one of the Jedi to the dark side of the Force. It will give him a powerful skill that allows to set all his parameters arbitrarily before every fight, with the restrictions that the parameters should remain non-negative integers and their sum should not change.

For every Jedi, determine how many other Jedi he can defeat being turned to the dark side.

Input

The first line contains a single integer $$$n$$$ ($$$1 \le n \le 500000$$$) — the number of the Jedi.

Each of the next $$$n$$$ lines contains three integers $$$a_i$$$, $$$b_i$$$ and $$$c_i$$$ ($$$0 \le a_i, b_i, c_i \le 10^9$$$) — the parameters of the Jedi.

Output

Output $$$n$$$ integers: how many other Jedi the $$$i$$$-th Jedi can defeat being turned to the dark side.

Example
Input
4
1 3 4
2 5 9
6 10 3
5 2 3
Output
1 3 3 2

K. Deck Sorting
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You have a deck of cards, lying on the table in front of you face up. The cards can be red, green and blue, and you know the order of cards in the deck. You want to sort the cards so that the cards of each color form a continuous segment. The order of colors doesn't matter.

The table doesn't have much free space — only for two piles of cards. In one turn, you take a top card from the deck and put it onto the top of one of the piles, face up. After all cards are distributed to the piles, you take one of these piles and put it onto the top of the other pile, again, face up.

Is it possible to sort the cards with the described procedure?

Input

The input contains a string of characters «R», «G» and «B». Its length is between $$$1$$$ and $$$1000$$$. The characters correspond to the colors of the cards in the deck, starting from the top one.

Output

Output «YES» or «NO», depending on if it's possible to sort the deck or not.

Examples
Input
RGBRGB
Output
YES
Input
RGBRGBRGB
Output
NO
Input
RBBRRB
Output
YES
Note

In the first sample the deck is «RGBRGB» (starting from the top card). The 1st, the 4th and the 5th cards can be put to the first pile (it will be «GRR»), and the 2nd, the 3rd and the 6th cards can be put to the second pile (it will be «BBG»). After that the second pile can be put to the top of the first one, and the deck becomes sorted: «BBGGRR».

L. Inscribed Circle
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given two circles on a plane. It is guaranteed that their circumferences have exactly two common points.

The result of the intersection of two circles is a figure with the positive area consisting of points belonging to both circles.

You have to inscribe a circle of the maximal possible radius into this figure. Output the coordinates of its center and its radius.

Input

The first line contains three integers $$$x_{1}$$$, $$$y_{1}$$$, $$$r_{1}$$$ ($$$-1000 \le x_{1}, y_{1} \le 1000, 1 \le r_{1} \le 1000$$$) — coordinates of the center of the first circle and its radius.

The second line contains three integers $$$x_{2}$$$, $$$y_{2}$$$, $$$r_{2}$$$ ($$$-1000 \le x_{2}, y_{2} \le 1000, 1 \le r_{2} \le 1000$$$) — coordinates of the center of the second circle and its radius.

Output

Output three real numbers $$$x$$$, $$$y$$$, $$$r$$$ — coordinates of the center and radius of the resulting circle. Each of the printed numbers should have absolute or relative error not exceeding $$$10^{-9}$$$.

Examples
Input
0 0 5
6 0 5
Output
3.000000000000000 0.000000000000000 2.000000000000000
Input
-12 34 56
78 -90 123
Output
13.322257821855908 -0.888444110112585 12.890601098820779

M. Shlakoblock is live!
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

User Shlakoblock has made a poll for the viewers of his channel, which game he should play on the next stream. $$$n$$$ games are presented in the poll. Every viewer can vote for any subset of these games, but it is not possible to vote for the same game more than once. In the end Shlakoblock will choose a random vote and will stream the game this vote was given for.

Everyone except you has already voted. Now the $$$i$$$-th game has $$$v_i$$$ votes. You estimate the pleasure of viewing the stream of the $$$i$$$-th game as $$$p_i$$$. Which games should you vote for to maximize the expected pleasure of the stream?

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 500$$$) — the number of test cases. Descriptions of the test cases follow.

In the first line of each test case there is a single integer $$$n$$$ ($$$1 \le n \le 1000$$$) — the number of games.

Each of the next $$$n$$$ lines of this test case contains two integers $$$p_i$$$ and $$$v_i$$$ ($$$0 \le p_i, v_i \le 1000$$$) — the pleasure of the stream of the $$$i$$$-th game and the number of votes it has now.

It is guaranteed that in every test at least one $$$v_i$$$ is positive.

Output

Output $$$3t$$$ lines. The answer for each test should consist of three lines.

In the first line output an irreducible fraction — the maximal possible expected pleasure of the stream.

In the second line output an integer $$$k$$$ ($$$0 \le k \le n$$$) — the number of games to vote for.

In the third line output $$$k$$$ distinct integers from $$$1$$$ to $$$n$$$ — the numbers of games to vote for.

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

Example
Input
2
5
10 5
4 7
6 3
8 2
2 4
4
1 1000
10 100
100 10
1000 1
Output
6/1
2
1 4 
2555/557
3
2 3 4