2018 BUPT Summer Training #1 (恢复训练) 部分题解(仍会更新)

原题链接

A. Treasure Island

Time limit: 2000 ms
Memory limit: 262144 kB

Pirate John Silver has found a map depicting exactly one island in a sea. The map is a piece of cloth divided into cells: n cells in height and m cells in width. John Silver knows that every cell denotes either land or water, but some of the cells are erased, and now it’s absolutely impossible to say what these cells represent.
Help John Silver to restore the map of the island. An island is a non-empty set of land cells connected in four directions (up, down, left and right).

Input

The first line contains two integers n and m (1 ≤ n, m ≤ 50) — the sizes of the map.
Each of the next n lines contains m characters and describes the map. A character is equal to «#» if this
cell is a water cell, «.» if it’s a land cell, and «?» if this cell is erased.
It’s guaranteed that the input contains at least one character «.» and at least one character «?».

Output

If it’s not possible to restore the map so that it would depict exactly one island, output «Impossible». If the map can be restored in a unique way, output n lines of m characters in the same format as they
are in the input, but replacing «?» with «.» or «#».
And if there are several correct ways to restore the map, output «Ambiguous».

Examples

Input

5 7
#######
#..#..#
#..?..#
#..#..#
#######

Output

#######
#..#..#
#…..#
#..#..#
#######

Input

5 7
#######
#…#.#
#.?.?.#
#.#…#
#######

Output

Ambiguous

Input

5 7
#######
#.#.#.#
#.#?#.#
#.#.#.#
#######

Output

Impossible

Solution

B. Repair

Time limit: 2000 ms
Memory limit: 262144 kB

Alex is repairing his country house. He has a rectangular metal sheet of size a × b. He has to cut two rectangular sheets of sizes a1 × b1 and a2 × b2 from it. All cuts must be parallel to the sides of the initial sheet. Determine if he can do it.

Input

The first line contains two space-separated integers a and b (1 ≤ a,b ≤ 109) — the sizes of the initial sheet.
The second line contains two space-separated integers a1 and b1 (1 ≤ a1, b1 ≤ 109) — the sizes of the first sheet to cut out.
The third line contains two space-separated integers a2 and b2 (1 ≤ a2, b2 ≤ 109) — the sizes of the second sheet to cut out.

Output

Output «YES» (without quotes), if it’s possible to cut two described sheets from the initial sheet, or «NO» (without quotes), if it’s not possible.

Example

Input

12 20
14 7
5 6

Output

YES

Input

12 20
11 9
20 7

Output

NO

Solution

C. Square Spiral Search

Time limit: 2000 ms
Memory limit: 65536 kB

A new computer scientist is trying to develop a new memory management system called “spiral memory management”.
The basic idea of this system is that it represents the memory as a 2D grid with a predefined origin point, and the address of each memory location is represented as its (x,y) coordinates, and it tries to store frequently used data as close to the origin point as possible.
This system needs a search algorithm. Our computer scientist is currently developing an algorithm called “square spiral search”.
The algorithm searches the memory locations in the following order (also shown in the figure):
(0,0), (1,0), (1,1), (0,1), (-1,1), (-1,0), (-1,-1), (0,-1), (1,-1), (2,-1), (2,0), (2,1), (2,2), (1,2), (0,2), (-1,2), (-2,2), (-2,1), (-2,0), (-2,-1), (-2,-2,) ,(-1,-2) … and so on.


Now he is wondering: how many steps would it take to reach a memory location with the address (x, y) using the square spiral search. Can you help him find the answer?

Input

The input starts with T the number of test cases, T test cases follows.
Each test case consists of two numbers: X, Y the address of the memory location.
 - 1, 000, 000, 000 ≤ X ≤ 1, 000, 000, 000
 - 1, 000, 000, 000 ≤ Y ≤ 1, 000, 000, 000

Output

For each test case print the number of steps it would take to reach the memory location ( x, y ) .

Examples

Input

3
1 0
1 1
-2 1

Output

1
2
17

Note

The number of steps to reach a memory location is defined as the number of memory locations searched before searching the requested location.

Solution

D. What a Mess

Time limit: 2000 ms
Memory limit: 65536 kB

Alex is a very clever boy, after all he is the son of the greatest watchmaker in Odin.
One day, Alex was playing with some old watches and he found n gears, each gear has ai teeth in it. Alex likes to make beautiful pairs of gears, he thinks a pair of gears is beautiful if we attach the two gears together and spin the first gear exactly one rotation, then the other gear spins an integer number of rotations. For example a pair of 8 and 4 is beautiful, whereas a pair of 8 and 5 isn’t, neither is pair of 4 and 8.
Now Alex is curious, he wants to know how many beautiful pairs are there. Counting is not Alex’s thing, so he asked you to help him.

Input

The first line of input contains one integer T: The number of test cases you need to process.
Each test case consists of two lines. The first line is a single integer n: the number of gears Alex has. The second line contains n space separated integers ai: the number if teeth in the ith gear.
1 ≤ n ≤ 104
2 ≤ ai ≤ 106

Output

For each testcase print a single integer: the number of distinct pairs that satisfy the problem statement.

Examples

Input

2
5
4 6 7 8 12
6
2 2 2 3 3 4

Output

3
7

Note

Note that we consider two pair distinct when they differ by at least one gear.
In the first sample the pairs are: (4,8) , (4,12) , (6,12)

Solution

E. Delete Them

Time limit: 2000 ms
Memory limit: 524288 kB

Polycarp is a beginner programmer. He is studying how to use a command line.
Polycarp faced the following problem. There are n files in a directory and he needs to delete some of them. Polycarp wants to run a single delete command with filename pattern as an argument. All the files to be deleted should match the pattern and all other files shouldn’t match the pattern.
Polycarp doesn’t know about an asterisk ‘*’, the only special character he knows is a question mark ‘?’ which matches any single character. All other characters in the pattern match themselves only.

Formally, a pattern matches a filename if and only if they have equal lengths and all characters in the corresponding positions are equal except when the character in the pattern is ‘?’, in which case the corresponding filename character does not matter.

For example, the filename pattern “a?ba?”:

matches filenames “aabaa”, “abba.”, “a.ba9” and “a.ba.”;
does not match filenames “aaba”, “abaab”, “aabaaa” and “aabaa.”.
Help Polycarp find a pattern which matches files to be deleted and only them or report if there is no such pattern.

Input

The first line of the input contains two integers n and m (1 ≤ m ≤ n ≤ 100) — the total number of files and the number of files to be deleted.
The following n lines contain filenames, single filename per line. All filenames are non-empty strings containing only lowercase English letters, digits and dots (‘.’). The length of each filename doesn’t exceed 100. It is guaranteed that all filenames are distinct.
The last line of the input contains m distinct integer numbers in ascending order a1, a2, …, am (1 ≤ ai ≤ n) — indices of files to be deleted. All files are indexed from 1 to n in order of their appearance in the input.

Output

If the required pattern exists, print “Yes” in the first line of the output. The second line should contain the required pattern. If there are multiple solutions, print any of them.
If the required pattern doesn’t exist, print the only line containing “No”.

Examples

Input

3 2
ab
ac
cd
1 2

Output

Yes
a?

Input

5 3
test
tezt
test.
.est
tes.
1 4 5

Output

Yes
?es?

Input

4 4
a
b
c
dd
1 2 3 4

Output

No

Input

6 3
.svn
.git
….

..
.
1 2 3

Output

Yes
.???

Solution

NULL

F. Car Repair Shop

Time limit: 2000 ms
Memory limit: 524288 kB

Polycarp starts his own business. Tomorrow will be the first working day of his car repair shop. For now the car repair shop is very small and only one car can be repaired at a given time.
Polycarp is good at marketing, so he has already collected n requests from clients. The requests are numbered from 1 to n in order they came.
The i-th request is characterized by two values: si — the day when a client wants to start the repair of his car, di — duration (in days) to repair the car. The days are enumerated from 1, the first day is tomorrow, the second day is the day after tomorrow and so on.
Polycarp is making schedule by processing requests in the order from the first to the n-th request. He schedules the i-th request as follows:
If the car repair shop is idle for di days starting from si (si, si + 1, …, si + di - 1), then these days are used to repair a car of the i-th client.
Otherwise, Polycarp finds the first day x (from 1 and further) that there are di subsequent days when no repair is scheduled starting from x. In other words he chooses the smallest positive x that all days x, x + 1, …, x + di - 1 are not scheduled for repair of any car. So, the car of the i-th client will be repaired in the range [x, x + di - 1]. It is possible that the day x when repair is scheduled to start will be less than si.
Given n requests, you are asked to help Polycarp schedule all of them according to the rules above.

Input

The first line contains integer n (1 ≤ n ≤ 200) — the number of requests from clients.
The following n lines contain requests, one request per line. The i-th request is given as the pair of integers si, di (1 ≤ si ≤ 109, 1 ≤ di ≤ 5·106), where si is the preferred time to start repairing the i-th car, di is the number of days to repair the i-th car.
The requests should be processed in the order they are given in the input.

Output

Print n lines. The i-th line should contain two integers — the start day to repair the i-th car and the finish day to repair the i-th car.

Examples

Input

3
9 2
7 3
2 4

Output

9 10
1 3
4 7

Input

4
1000000000 1000000
1000000000 1000000
100000000 1000000
1000000000 1000000

Output

1000000000 1000999999
1 1000000
100000000 100999999
1000001 2000000

Solution

NULL

G. Potions Homework

Time limit: 1000 ms
Memory limit: 262144 kB

Harry Water, Ronaldo, Her-my-oh-knee and their friends have started a new school year at their MDCS School of Speechcraft and Misery. At the time, they are very happy to have seen each other after a long time. The sun is shining, birds are singing, flowers are blooming, and their Potions class teacher, professor Snipe is sulky as usual. Due to his angst fueled by disappointment in his own life, he has given them a lot of homework in Potions class.
Each of the n students has been assigned a single task. Some students do certain tasks faster than others. Thus, they want to redistribute the tasks so that each student still does exactly one task, and that all tasks are finished. Each student has their own laziness level, and each task has its own difficulty level. Professor Snipe is trying hard to improve their work ethics, so each student’s laziness level is equal to their task’s difficulty level. Both sets of values are given by the sequence a, where ai represents both the laziness level of the i-th student and the difficulty of his task.
The time a student needs to finish a task is equal to the product of their laziness level and the task’s difficulty. They are wondering, what is the minimum possible total time they must spend to finish all tasks if they distribute them in the optimal way. Each person should receive one task and each task should be given to one person. Print the answer modulo 10 007.

Input

The first line of input contains integer n (1 ≤ n ≤ 100 000) — the number of tasks. The next n lines contain exactly one integer number ai (1 ≤ ai ≤ 100 000) — both the difficulty of the initial task and the laziness of the i-th students.

Output

Print the minimum total time to finish all tasks modulo 10 007.

Example

Input

2
1
3

Output

6

Note

In the first sample, if the students switch their tasks, they will be able to finish them in 3 + 3 = 6 time units.

Solution

H. Paint it really, really dark gray

Time limit: 1000 ms
Memory limit: 262144 kB

I see a pink boar and I want it painted black. Black boars look much more awesome and mighty than the pink ones. Since Jaggy became the ruler of the forest, he has been trying his best to improve the diplomatic relations between the forest region and the nearby ones.
Some other rulers, however, have requested too much in return for peace between their two regions, so he realized he has to resort to intimidation. Once a delegate for diplomatic relations of a neighboring region visits Jaggy’s forest, if they see a whole bunch of black boars, they might suddenly change their mind about attacking Jaggy. Black boars are really scary, after all.
Jaggy’s forest can be represented as a tree (connected graph without cycles) with n vertices. Each vertex represents a boar and is colored either black or pink. Jaggy has sent a squirrel to travel through the forest and paint all the boars black. The squirrel, however, is quite unusually trained and while it traverses the graph, it changes the color of every vertex it visits, regardless of its initial color: pink vertices become black and black vertices become pink.
Since Jaggy is too busy to plan the squirrel’s route, he needs your help. He wants you to construct a walk through the tree starting from vertex 1 such that in the end all vertices are black. A walk is a sequence of vertices, such that every consecutive pair has an edge between them in a tree.

Input

The first line of input contains integer n (2 ≤ n ≤ 200 000), denoting the number of vertices in the tree. The following n lines contains n integers, which represent the color of the nodes.
If the i-th integer is 1, if the i-th vertex is black and  - 1 if the i-th vertex is pink.
Each of the next n - 1 lines contains two integers, which represent the indexes