XXVII Interregional Programming Olympiad, Vologda SU, 2025
A. Space Drawings
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The fence consists of $$$N$$$ boards. On Cosmonautics Day, Petya drew a spaceship on every fourth board (4, 8, 12 ...). Vasya drew a lunar rover on every fifth board (5, 10, 15 ...). Masha drew an orbital station on every sixth board (6, 12, 18 ...).

Determine the number of boards with only one drawing.

Input

An integer $$$N$$$ ($$$1 \le N \le 10^9$$$) is given.

Output

Your program should output a single integer — the number of boards with one drawing.

Example
Input
15
Output
6

B. Fuel Consumption
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Student Vasily bought a new car. Well, almost new. After all, is 10 years really an age for a good car?

After driving a bit, Vasily began to suspect that his car consumes somewhat more gasoline than stated in the specifications. To measure the consumption, he conducted the following experiment.

First, he filled the tank full, then drove $$$A$$$ kilometers in the city and $$$B$$$ kilometers on the highway, and filled the tank full again. At that time, $$$P$$$ liters of gasoline fit into the tank. Then he drove $$$C$$$ kilometers in the city and $$$D$$$ kilometers on the highway and filled the tank full again. At that time, $$$Q$$$ liters of gasoline fit into it.

Determine the fuel consumption per 100 kilometers in the city and on the highway.

Input

The first line contains three integers $$$A$$$, $$$B$$$, $$$P$$$ ($$$0 \le A, B \le 1000$$$, $$$100 \le A + B \le 1000$$$, $$$5 \le P \le 100$$$).

The second line contains three integers $$$C$$$, $$$D$$$, $$$Q$$$ ($$$0 \le C, D \le 1000$$$, $$$100 \le C + D \le 1000$$$, $$$5 \le Q \le 100$$$).

Output

If the input data allows for a unique answer, and both numbers in the answer are positive, then output the word "Success" on the first line, and on the second line output two real numbers — how many liters of gasoline the car will consume when driving 100 kilometers in the city and when driving 100 kilometers on the highway. The absolute or relative error must not exceed $$$10^{-1}$$$.

If the input data is contradictory, then output "Contradiction".

If the input data is consistent, the answer is unique, but at least one of the numbers in the answer is not positive, then output "Not positive".

If the input data is consistent but does not allow for a unique answer, then output "Ambiguity".

Examples
Input
250 150 49
200 200 46
Output
Success
14.500 8.500
Input
100 100 50
100 100 30
Output
Contradiction
Input
100 100 50
100 100 50
Output
Ambiguity
Input
100 900 100
900 100 10
Output
Not positive
Note

A situation where the car consumes more fuel on the highway than in the city is not considered an error.

C. Car Trip
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In a certain region, there are $$$n$$$ cities. Some pairs of cities are connected by bidirectional roads. Any two cities are connected directly by no more than one road.

Student Vasily wants to drive from city 1 to city $$$n$$$ in his car. He has already calculated how many liters of gasoline are needed to travel each road in his car.

Gas stations are only available in cities. However, Vasily can take as many canisters as he wants, so he can refuel any amount of gasoline in any city. Initially, he is at a gas station in the first city, and he has zero liters of gasoline.

The price per liter of gasoline may vary in different cities. Determine the minimum amount of money Vasily needs to spend to get from city 1 to city $$$n$$$. Also, determine his route and how many liters of gasoline he should buy in each city along the way.

Input

The first line contains two integers $$$n$$$ and $$$m$$$ — the number of cities and the number of roads ($$$2 \le n \le 1000$$$, $$$0 \le m \le 10000$$$).

The next line contains $$$n$$$ integers $$$c_i$$$ — the cost of one liter of gasoline in each city ($$$1 \le c_i \le 100$$$).

The following $$$m$$$ lines contain information about the roads — triples of integers $$$u_i$$$, $$$v_i$$$, and $$$f_i$$$, where $$$u_i$$$ and $$$v_i$$$ are the cities connected by the respective road ($$$1 \le u_i, v_i \le n$$$, $$$u_i \ne v_i$$$), and $$$f_i$$$ is the amount of gasoline required to travel this road ($$$1 \le f_i \le 100$$$).

Output

If it is possible to get from city 1 to city $$$n$$$, then output in the first line the minimum amount of money that must be spent on gasoline. In the second line, output the integer $$$k$$$ — the number of cities in the found route. In the following $$$k$$$ lines, output pairs of integers — the number of each city in order and the amount of gasoline that needs to be bought in that city. If there are multiple correct answers, output any.

If it is not possible to get from city 1 to city $$$n$$$, output -1.

Examples
Input
5 5
50 40 10 100 75
1 2 4
1 4 3
2 5 9
3 4 5
4 5 10
Output
550
5
1 8
4 0
3 15
4 0
5 0
Input
4 2
10 20 30 40
1 2 50
3 4 100
Output
-1
Note

The illustration for the first example:

Next to the vertices are the gasoline prices, and next to the edges are the consumption in liters. In the example, we refuel 8 liters in city 1, go to city 4, then go to city 3 for cheaper gasoline and refuel 15 liters there, return to city 4, and go to city 5.

D. Mines
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$n$$$ mines installed along the straight road. Mine number $$$i$$$ is located at the coordinate $$$x_i$$$ and has a blast radius of $$$d_i$$$. When this mine explodes, all mines with coordinates from $$$x_i - d_i$$$ to $$$x_i + d_i$$$ inclusive will also explode (and they, in turn, may cause other mines to explode, and so on).

Determine how many mines will explode in total if mine number $$$k$$$ is detonated.

Input

The first line of input contains an integer $$$n$$$ ($$$1 \le n \le 10^5$$$).

The second line contains $$$n$$$ distinct integers $$$x_1$$$, $$$x_2$$$, ..., $$$x_n$$$ in increasing order ($$$0 \le x_i \le 10^9$$$).

The third line contains $$$n$$$ integers $$$d_1$$$, $$$d_2$$$, ..., $$$d_n$$$ ($$$0 \le d_i \le 10^9$$$).

The fourth line contains an integer $$$k$$$ ($$$1 \le k \le n$$$).

Output

Output a single integer — the number of exploded mines.

Example
Input
5
0 10 30 50 100
40 10 25 20 10
2
Output
4
Note

In the example, the second mine will cause the first to explode, the first will cause the third to explode, and the third will cause the fourth to explode.

E. Messenger
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

This is a double-launch problem.

The IT company "Crutches and Bicycles" has developed a new text messenger that allows users to exchange messages in the form of strings composed of uppercase Latin letters with a length of no more than 1000 characters.

Unfortunately, there is a bug in the code: when transmitting a message, one of the letters may unexpectedly be replaced by some other letter. The developers cannot find the bug in the code, so they decided to implement a "crutch": to encode messages in such a way that they can be uniquely restored under the condition that no more than one letter has been corrupted. At the same time, the developers want the encoded string to also consist only of uppercase Latin letters, and its length should exceed the length of the original string by no more than 10 characters.

Develop a method for encoding and decoding that meets these requirements.

Input

The first line of the input contains a number $$$t$$$, equal to 1 or 2.

If $$$t=1$$$, then the second line of input contains the message that needs to be encoded. It consists of uppercase Latin letters and has a length of 1 to 1000 characters.

If $$$t=2$$$, then the second line of input contains a previously encoded message by your program that needs to be decoded. No more than one character in this string may have been replaced by any uppercase Latin letter.

Output

Output a single string of uppercase Latin letters — the encoded or decoded message.

Example
Input
1
ABC
Output
AAABBBCCC
Input
2
AXABBBCCC
Output
ABC

F. Sorting by One Swap
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

A permutation of natural numbers from 1 to $$$n$$$ is given. Find two non-overlapping segments such that if they are swapped, the permutation becomes sorted in ascending order.

Input

The first line of the input contains an integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$).

The second line contains a permutation of integers from 1 to $$$n$$$, with numbers separated by spaces.

Output

If a solution exists, output four integers $$$pos_1$$$, $$$len_1$$$, $$$pos_2$$$, and $$$len_2$$$, where $$$pos_1$$$ is the position of the first element of the first segment (numbering starts from one), $$$len_1$$$ is the length of the first segment, $$$pos_2$$$ and $$$len_2$$$ are the same for the second segment. The inequality $$$pos_1 \lt pos_2$$$ must hold.

If no solution exists, output a single number -1.

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

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

A valid arithmetic expression is given, which can contain only integers in the range from 0 to 9, parentheses, and the binary operators '+' and '-'.

Remove zero or more parentheses so that the expression remains valid and its value is maximized.

Input

A single line of input contains a valid expression in the format described above, containing no more than 100 numbers and no more than 100 parentheses.

Output

In the first line of output, print the maximum value of the expression. In the second line, print the expression after removing the parentheses that yields this value.

Examples
Input
1+(2)-(3-(4-5))
Output
9
1+(2)-(3-4-5)
Input
1-(2-3)
Output
2
1-(2-3)

H. Pair of Neighbors
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Natural numbers from 1 to $$$n$$$ are written on the board. It is required to select some of them so that among the selected numbers there is exactly one pair of neighbors (numbers that differ by one). Determine how many ways this can be done.

For example, for $$$n=4$$$, the answer is 5 — these are the following 5 ways: {1, 2}, {2, 3}, {3, 4}, {1, 2, 4}, {1, 3, 4}.

Input

One integer $$$n$$$ ($$$1 \le n \le 10^6$$$) is given.

Output

Output one integer — the number of ways modulo $$$10^9+7$$$ (that is, the remainder of the number of ways divided by $$$10^9+7$$$).

Example
Input
4
Output
5

I. Casino
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

This is an interactive problem.

Agent 008 is playing roulette at a casino. In each round, he bets on a color (red or black). In case of a loss, the casino takes the bet, and in case of a win, the bet is returned doubled. It is known that the agent never loses more than three times in a row.

Before going to the casino, the agent received 200 pounds at the cashier. Additionally, he found a crumpled tenner in his pocket, so he ended up with an initial amount of 210 pounds. Help him increase this amount to 1000 pounds (or more) by playing no more than 100 times.

Interaction

Your program should repeatedly do the following.

Output a positive integer — the amount of the bet (this amount must be available), then a space and the letter R or B (R — red, B — black) followed by a newline. Immediately after outputting, flush the buffer to the standard output (see the note).

After that, input a single integer — the result of the round. This number will be 0, 1, or -1, where 0 — loss, 1 — win, -1 — error (invalid bet or color). If the result is -1, terminate the program. Also terminate the program if the current amount becomes greater than or equal to 1000. Otherwise, continue playing.

Example input-output: 

output:
1 R
input:
0
output:
2 B
input: 
1
...(and so on)
Note

It is not guaranteed that the casino plays fairly, meaning the color may not come up randomly. However, it is guaranteed that after three consecutive losses, there will definitely be a win.

Flushing the output buffer to the output stream in different languages is done as follows:

  • In C++, it is sufficient to output std::endl or std::flush after outputting to cout (the first option will also automatically make a linebreak).
  • In Java, after each output, you need to use the flush method on the output stream, for example: System.out.flush();
  • In Python, you can import the sys module and call sys.stdout.flush() after each output.
  • In Pascal, you can call flush(output); after each output.
  • In C#, you can call Console.Out.Flush(); after each output.

J. Sum of Squares
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

For a given natural number $$$n$$$, find $$$n+1$$$ positive integers, not exceeding $$$10^9$$$, such that the sum of the squares of the first $$$n$$$ of these numbers equals the square of the last one.

Input

An integer $$$n$$$ is given ($$$1 \le n \le 1000$$$).

Output

Output $$$n+1$$$ integers in the range from 1 to $$$10^9$$$. If there are multiple correct answers, output any. If there are no solutions, output the number -1.

Example
Input
2
Output
3 4 5

K. Secret Level
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Petya loves playing computer games. He is currently playing yet another game and has just discovered a door to a secret level.

Next to the door, there is a square grid of size $$$n$$$ x $$$n$$$ cells. Some cells are black, and the others are white. If he clicks on any cell, its color will change to the opposite (black to white and white to black). At the same time, the colors of all neighboring (adjacent on the side) cells will also change. The door will open if all cells become the same color.

Help Petya open the door by making the minimum number of clicks.

Input

The first line of input contains an integer $$$n$$$ ($$$2 \le n \le 20$$$). The following $$$n$$$ lines contain $$$n$$$ characters each, either 'b' or 'w', where 'b' represents black color and 'w' represents white.

Output

If a solution exists, first output an integer $$$m$$$ — the minimum number of clicks. In each of the following $$$m$$$ lines, output the coordinates of the cell to be clicked — a pair of integers $$$y_i$$$ and $$$x_i$$$, where $$$y_i$$$ is the row number and $$$x_i$$$ is the column number. Rows are numbered from top to bottom, columns from left to right, numbering starts from one. If there are multiple correct answers, output any.

If there is no solution, output a single number -1.

Examples
Input
2
wb
bw
Output
2
1 2
2 1
Input
3
bbb
bbb
bbb
Output
0
Input
4
bbbb
wwwb
bbbb
bwww
Output
-1
Note

Illustration for the first example: