2018, XI Samara Regional Intercollegiate Programming Contest
A. Restoring Numbers
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Pavel had two positive integers a and b. He found their sum s and greatest common divisor g, and forgot a and b after that. Help him to restore the original numbers.

Input

A single line contains two integers s and g (1 ≤ s ≤ 109, 1 ≤ g ≤ 109) — sum and greatest common divisor of the numbers a and b.

Output

If Pavel made a mistake and there are no such numbers a and b, output a single number  - 1.

Otherwise, output two positive integers a and b on a single line, separated by a space. If there are multiple possible solutions, output any of them.

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

B. Minimal Area
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a strictly convex polygon. Find the minimal possible area of non-degenerate triangle whose vertices are the vertices of the polygon.

Input

The first line contains a single integer n (3 ≤ n ≤ 200000) — the number of polygon vertices.

Each of the next n lines contains two integers xi and yi ( - 109 ≤ xi, yi ≤ 109) — the coordinates of polygon vertices.

The polygon is guaranteed to be strictly convex. Vertices are given in the counterclockwise order.

Output

It is known that the area of triangle whose vertices are the integer points on the grid is either integer or half-integer.

Output a single integer — the required area, multiplied by 2.

Examples
Input
4
0 1
3 0
3 3
-1 3
Output
5
Input
3
0 0
1 0
0 1
Output
1
Input
4
-999999991 999999992
-999999993 -999999994
999999995 -999999996
999999997 999999998
Output
3999999948000000156
Note

It is recommended to make all calculations using integer numbers, because floating point precision most likely would not be enough.

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

Pavel is developing a game. To do that, he needs functions available in a third-party library too famous to be called. It is known that the function i first appeared in version ai and existed until version bi, and starting from the version bi + 1, it is absent in this library.

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

Input

The first line contains a single integer n (1 ≤ n ≤ 200000) — the number of the functions.

Each of the next n lines contains two integers ai and bi (1 ≤ ai ≤ bi ≤ 109) — the interval of library versions where function i was available.

Output

In the first line output a single integer k — the minimal number of library versions need to be purchased to unlock all functions.

In the second line output k distinct integers — the numbers of versions need to be purchased.

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

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

D. Transfer Window
time limit per test
2 s
memory limit per test
256 megabytes
input
standard input
output
standard output

You play a football manager. There are n football players in the game, and k of them — a1, a2, ..., ak — are currently playing in your team. You want players b1, b2, ..., bk to play in your team. To achieve that, you can suggest other teams to exchange one of your players to their player.

For each ordered pair of distinct players (x, y) it is known whether or not a team controlled by AI would accept to exchange your player x to their player y. Determine whether it is possible to collect a team consisting of football players b1, b2, ..., bk and if it is, output the order of exchanges to achieve it.

Input

The first line contains two integers n and k (1 ≤ n ≤ 300, 1 ≤ k ≤ n) — the total number of football players in the game and the number of football players in your team.

The second line contains k distinct integers ai (1 ≤ ai ≤ n) — the players currently playing in your team.

The third line contains k distinct integers bi (1 ≤ bi ≤ n) — the players you want to see in your team.

Each of the next n lines contains n characters. Character in i-th line and j-th column equals «1», if the team controlled by AI would accept to exchange your player i to their player j, and «0», if it wouldn't. Characters on the main diagonal are equal to zero.

Output

In the first line output «YES», if it's possible to make a team of players b1, b2,  ..., bk, and «NO», if it's not.

In the case of the «YES» answer, in the second line output a single integer q (0 ≤ q ≤ n·n) — the number of exchanges, and then q lines — the sequence of exchanges. Each of these q lines must contain two distinct integers xj and yj (1 ≤ xj ≤ n, 1 ≤ yj ≤ n) — the number of player from your team you want to exchange and the number of player from another team you want to get for him. Please note that after j-th exchange player yj becomes a player of your team and player xj leaves your team.

If there are several sequences of exchanges leading to the desired result, output any of them. Also note that it's not required to minimize the number of exchanges, it's just enough if it doesn't exceed n·n.

Examples
Input
5 2
1 2
4 5
00100
00100
00011
00000
00000
Output
YES
4
1 3
3 4
2 3
3 5
Input
3 2
1 2
2 3
000
001
010
Output
NO

E. Substring Reverse
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Two strings s and t of the same length are given. Determine whether it is possible to make t from s using exactly one reverse of some its substring.

Input

The first line contains the string s, and the second — the string t. Both strings have the same length from 1 to 200000 characters and consist of lowercase Latin letters.

Output

Output «YES», if it is possible to reverse some substring of s to make s equal to t, and «NO», otherwise.

Examples
Input
abcdefg
abedcfg
Output
YES
Input
abcdefg
abdecfg
Output
NO

F. Tree Restoration
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There is a tree of n vertices. For each vertex a list of all its successors is known (not only direct ones). It is required to restore the tree or to say there is no such tree.

Input

The first line contains a single integer n (1 ≤ n ≤ 1000) — the number of vertices in the tree.

Each of the next n lines contains an integer ci (0 ≤ ci ≤ n) — the number of successors of vertex i, and then ci distinct integers aij (1 ≤ aij ≤ n) — the indices of successors of vertex i.

Output

If the answer does not exist, output «NO».

Otherwise, in the first line output «YES», and then output n - 1 lines containing two integers each — indices of parent and child. Pairs (parent, child) can be output in any order.

Examples
Input
5
4 2 3 4 5
3 3 4 5
2 4 5
1 5
0
Output
YES
1 2
2 3
3 4
4 5
Input
5
4 2 3 4 5
3 3 4 5
0
1 5
0
Output
YES
1 2
2 3
2 4
4 5
Input
3
3 2 3 1
3 3 1 2
3 1 2 3
Output
NO

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

Let us call underpalindromity of array b of length k the minimal number of times one need to increment some elements bj by 1 so that the array b would become a palindrome, that is, b1 = bk, b2 = bk - 1, and so on.

The array of length n, consisting of integers, is given. Consider all its subarrays of length k, and for each of these subarrays its underpalindromity pi. It's needed to calculate sum of all pi (1 ≤ i ≤ n - k + 1).

Input

The first line contains two integers n and k (1 ≤ k ≤ n ≤ 200000) — the length of the array and the length of subarrays.

The second line contains n integers ai ( - 108 ≤ ai ≤ 108) — the elements of the array.

Output

Output a single integer — sum of underpalindromities of all subarrays of length k.

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

H. Safe Path
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You play a new RPG. The world map in it is represented by a grid of n × m cells. Any playing character staying in some cell can move from this cell in four directions — to the cells to the left, right, forward and back, but not leaving the world map.

Monsters live in some cells. If at some moment of time you are in the cell which is reachable by some monster in d steps or less, he immediately runs to you and kills you.

You have to get alive from one cell of game field to another. Determine whether it is possible and if yes, find the minimal number of steps required to do it.

Input

The first line contains three non-negative integers n, m and d (2 ≤ n·m ≤ 200000, 0 ≤ d ≤ 200000) — the size of the map and the maximal distance at which monsters are dangerous.

Each of the next n lines contains m characters. These characters can be equal to «.», «M», «S» and «F», which denote empty cell, cell with monster, start cell and finish cell, correspondingly. Start and finish cells are empty and are presented in the input exactly once.

Output

If it is possible to get alive from start cell to finish cell, output minimal number of steps required to do it. Otherwise, output «-1».

Examples
Input
5 7 1
S.M...M
.......
.......
M...M..
......F
Output
12
Input
7 6 2
S.....
...M..
......
.....M
......
M.....
.....F
Output
11
Input
7 6 2
S.....
...M..
......
......
.....M
M.....
.....F
Output
-1
Input
4 4 2
M...
.S..
....
...F
Output
-1
Note

Please note that monsters can run and kill you on start cell and on finish cell as well.

I. Guess the Tree
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Jury has a complete binary tree with n = 2h - 1 vertices. Its vertices are numbered with distinct integers from 1 to n, but you don't know which vertices are connected with which.

You can ask a jury's program, what is the distance between some two vertices. You must restore tree structure with at most 2.5·h·n such queries.

Interaction

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

In the very beginning your program gets a single integer n (1 ≤ n ≤ 1023, n + 1 is the power of two) — the number of vertices in the tree.

After that you can make at most 2.5·h·n queries. To make a query, output character «?» and two integers from 1 to n — numbers of vertices x and y you want to know the distance between. As a response a single integer will be given to you — the distance between vertices x and y.

Once you find out a complete tree structure, output character «!», and then n integers pi, where pi is the parent of vertex i or 0 if i is the root of the tree. After this your program must terminate.

Example
Input
<interactor's output>

? 1 2

<interactor's output>

? 2 3

<interactor's output>

! 2 0 2
Output
3

<solution's output>

1

<solution's output>

1

<solution's output>
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.

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

There are n sticks, the i-th of which has length ai. Alex wants to assemble from them as many parallelograms as possible simultaneously, with each stick used at most in one parallelogram. What maximal number of parallelograms is it possible to assemble?

Input

The first line contains a single integer n (1 ≤ n ≤ 200000) — the number of sticks.

The second line contains n integers ai (1 ≤ ai ≤ 200000) — the lengths of sticks.

Output

Output a single integer — the maximal number of parallelograms that is possible to assemble.

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

K. Video Reviews
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The studio «Lodka Gaming» is engaged in advertising of their new game «.C.O.N.T.E.S.T: Unexpected Behaviour». The studio's marketer is planning to communicate with n videobloggers one by one (in the predetermined order, starting from the 1-st and ending with the n-th), offering them to record a video review on the game. All people are different and videobloggers are as well, therefore the i-th videoblogger will record a review in two cases: either he is interested in this game, or there are already at least ai video reviews on this game.

The studio wants to have at least m video reviews in the Internet. The game designer of «Lodka Gaming» understands these video reviews possibly would not appear by themselves, so he wants to convince some video bloggers that they are actually interested in this game. Which minimal number of videobloggers are needed to be convinced?

Input

The first line contains two integers n and m (1 ≤ n ≤ 200000, 1 ≤ m ≤ n) — the number of videobloggers and the required number of video reviews.

The second line contains n integers ai (0 ≤ ai ≤ 200000) — the minimal number of video reviews that should appear in the Internet so that the i-th videoblogger will record a review in case he is not interested in the game.

Output

Output a single integer — the minimal number of videobloggers who have to be convinced to record a video review on the game in order to achieve at least m total video reviews in the Internet.

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

L. Queries on a String
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

A string s is given. Also there is a string p, and initially it is empty. You need to perform q operations of kind «add a letter to the end of the string p» and «remove a letter from the end of the string p», and after performing each operation you must say whether or not s contains p as a subsequence.

Input

The first line contains the string s of length from 1 to 200000, consisting of lowercase Latin letters.

The second line contains a single integer q (1 ≤ q ≤ 200000) — the number of operations.

Each of the next q lines describes an operation in the format «push c», which means «add letter c to the end of the string p» (c is lowercase Latin letter), or «pop», which means «remove letter from the end of the string p». The «pop» operations is guaranteed never to be applied to the empty string p.

Output

Output q lines, each of which equals «YES» or «NO», depending on whether or not the string p is contained in the string s as a subsequence after performing the corresponding operation.

Example
Input
abcabc
30
push a
pop
push a
push a
push a
pop
push c
push b
pop
pop
push b
push c
push c
pop
pop
pop
pop
push b
push c
push c
pop
push b
push c
pop
pop
push a
push b
push c
push a
pop
Output
YES
YES
YES
YES
NO
YES
YES
NO
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES

M. Forgotten Spell
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Three mages are trying to remember a spell. Each of them believes the spell is some string of length n and it is known that each of the mages is mistaken in at most one letter. It is required to restore the forgotten spell.

Input

Three strings of the same length n (1 ≤ n ≤ 200000) are given in the input. They consist of lowercase Latin letters.

Output

If such a situation is not possible, output «Impossible».

If there are several spells satisfying the conditions, output «Ambiguous».

Finally, if the forgotten spell is the only one possible, output it.

Examples
Input
aab
aca
daa
Output
aaa
Input
abc
aca
abc
Output
Ambiguous
Input
abcde
fghij
klmno
Output
Impossible