XXVIII Interregional Programming Olympiad, Vologda SU, 2026
A. Squares and Triangles
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Several geometric figures are arranged in a row. Among them there are two triangles, and all the others are squares. It is known that to the right of the first triangle there are the second triangle and $$$a$$$ squares, and to the left of the second triangle there are the first triangle and $$$b$$$ squares. Determine the minimum and maximum possible number of figures for which this situation is possible.

Input

Two integers $$$a$$$ and $$$b$$$ are given, each on a separate line ($$$0 \le a, b \le 10^9$$$).

Output

Output two integers — the minimum and the maximum possible number of figures.

Example
Input
2
3
Output
5 7

B. Pair Partitioning
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Determine in how many ways the natural numbers from $$$1$$$ to $$$2n$$$ can be partitioned into $$$n$$$ pairs so that in each pair, the second number was at least twice the first

Input

The only line of the input contains an integer $$$n$$$ ($$$1 \le n \le 25$$$).

Output

Print one integer — the answer.

Example
Input
3
Output
2
Note

In the example, two valid sets of pairs can be formed: 1 – 5, 2 – 4, 3 – 6 and 1 – 4, 2 – 5, 3 – 6.

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

You are given a set of $$$n$$$ integers. Determine the minimum number of integers that must be added to this set so that all numbers can be arranged into an arithmetic progression.

Explanation: a sequence of numbers forms an arithmetic progression if all differences between adjacent elements are equal.

Input

The first line contains an integer $$$n$$$ — the number of numbers ($$$1 \le n \le 10^5$$$). The next $$$n$$$ lines contain integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$).

Output

Print one integer — the minimum number of integers that must be added to the input set. If there is no solution, print -1.

Example
Input
3
-2
7
1
Output
1
Note

In the example, you can add the number 4, then the sequence -2 1 4 7 forms an arithmetic progression.

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

A combination lock contains several dials. Each dial is marked with numbers from 0 to 9 (after 9 comes 0 again).

In one action, you can grasp one or two adjacent dials with your fingers and rotate them together at any angle. Determine the minimum number of such actions required to open the lock.

Input

The first line of the input data contains the initial code on the lock. The second line contains the code to open the lock. The lengths of the lines are equal and do not exceed $$$10^5$$$.

Output

Print one integer — the minimum number of actions to open the lock.

Example
Input
0000
7329
Output
3
Note

In the example, you can proceed as follows. Rotate the first (top) disk to get the code 7000. Then rotate the second and third disks simultaneously to get the code 7330. Finally, rotate the last two disks simultaneously to get the code 7329. A total of 3 steps.

E. Colored Balls - 1
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$n$$$ balls arranged in a row. Each ball is painted in one of three possible colors. In one operation, you may swap any two balls.

Determine the minimum number of such swaps required so that, in the end, all balls of the same color stand consecutively. In other words, there must not be two balls of the same color with balls of other colors between them.

Input

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

The second line contains $$$n$$$ integers from $$$1$$$ to $$$3$$$ — the colors of the balls.

Output

Print one integer — the minimum number of swaps.

Example
Input
5
2 1 2 2 1
Output
1

F. Colored Balls - 2
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$n$$$ balls arranged in a row. Each ball is painted in one of ten possible colors. In one operation, you can swap two adjacent balls.

Determine the minimum number of such swaps required so that, in the end, all balls of the same color stand consecutively. In other words, there must not be two balls of the same color with balls of other colors between them.

Input

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

The second line contains $$$n$$$ integers from $$$1$$$ to $$$10$$$ — the colors of the balls.

Output

Print one integer — the minimum number of swaps.

Example
Input
4
2 1 2 1
Output
1

G. Self-Synchronizing Code
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

This is a double-run problem.

In a physics lab, students developed a device that allows transmitting text messages consisting of lowercase Latin letters using a laser. Before sending, a message is converted into binary code and then transmitted sequentially, bit by bit.

However, during testing of the device, a problem was discovered. It turned out that if four identical bits in a row appear during transmission (that is, «0000» or «1111»), synchronization is lost on the receiving side. Therefore, it is necessary to come up with an encoding method for which this situation is impossible. The developers also want the number of bits in the encoded message to exceed the length of the original message by no more than six times.

Develop some encoding and decoding method satisfying these requirements.

Input

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

If $$$t=1$$$, then the second input line contains the message that must be encoded. It consists of lowercase Latin letters and has length from 1 to 10000 characters.

If $$$t=2$$$, then the second input line contains a message previously encoded by your program, which must be decoded.

Output

Print one line — the encoded or decoded message.

Example
Input
1
aba
Output
100101101101100101
Input
2
100101101101100101
Output
aba

H. No More Than Two in a Row
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is an interactive problem.

The playing field is a strip one cell wide and $$$n$$$ cells long. Two players take turns making moves. On each move, an empty cell is chosen and marked with a cross. It is forbidden for the field to contain more than two consecutive crosses. The player who has no legal move loses.

Write a program that plays against the jury's program. Your program must win all rounds. This is always possible, since you choose who makes the first move.

Interaction

First, input an integer $$$n$$$ ($$$1 \le n \le 30$$$) — the length of the strip.

Next, decide who makes the first move. Output 1 if you move first; otherwise output 2. Then output a newline and flush the standard output buffer.

After that, your program must repeatedly do the following.

  • If it is your turn, output one integer from $$$1$$$ to $$$n$$$ — the cell where you place a cross. Then output a newline and flush the standard output buffer. If there is no legal move, output 0 and terminate the program.
  • If it is the opponent's turn, input one integer from $$$0$$$ to $$$n$$$. If the input number is greater than zero, then it is the cell where the opponent moved. If the input number is 0, then the game is over — terminate the program.

Example input-output:

InputOutput
4
1
4
2
1
0

Note

To flush the buffer use:

  • cout.flush(); or cout << flush; or cout << endl; — for C++ (the latter will also output a newline)
  • fflush(stdout); — for C or C++ with the old output style
  • sys.stdout.flush() — for Python (you need to import the sys module)
  • System.out.flush(); — for Java
  • Console.Out.Flush(); — for C#
  • flush(output); — for Pascal

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

Consider a square matrix $$$a$$$ of size $$$n$$$ consisting only of zeros and ones.

Apply the following algorithm to it: while there exist indices $$$i$$$, $$$j$$$, $$$k$$$ (not necessarily distinct) such that $$$a[i][j]=1$$$, $$$a[j][k]=1$$$, and $$$a[i][k]=0$$$, replace $$$a[i][k]$$$ with $$$1$$$. The resulting matrix is called the transitive closure of matrix $$$a$$$.

For the given matrix $$$a$$$, find a matrix $$$b$$$ such that it contains the minimum possible number of ones, and its transitive closure is equal to the transitive closure of matrix $$$a$$$.

Input

The first line of the input contains an integer $$$n$$$ ($$$1 \le n \le 100$$$).

Each of the next $$$n$$$ lines contains $$$n$$$ numbers 0 or 1 — the elements of matrix $$$a$$$.

Output

Output the required matrix $$$b$$$. If there are several correct answers, output any of them.

Example
Input
3
1 1 1
1 0 1
0 0 1
Output
0 1 0
1 0 1
0 0 1
Note

The matrices from the example have the following transitive closure: 

1 1 1
1 1 1
0 0 1

J. Valuable Prizes
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

At the opening of the olympiad, each participant was given a pen and a notepad. Since, due to budget "optimization", it was not possible to buy any other prizes, so the jury decided to award each awardee with another $$$a$$$ pens and $$$b$$$ notepads, and each winner — with $$$2a$$$ pens and $$$2b$$$ notepads.

Determine the minimum possible number of people who could have participated in the olympiad, if in total $$$c$$$ pens and $$$d$$$ notepads were distributed.

Explanation: the sets of awardees and winners do not intersect.

Input

The input data contain four integers $$$a$$$, $$$b$$$, $$$c$$$, and $$$d$$$ ($$$1 \le a, b, c, d \le 10^{18}$$$), each integer on a separate line.

Output

Print one integer — the minimum possible number of participants. If there is no solution, print 0.

Examples
Input
2
3
10
12
Output
6
Input
2
3
1
2
Output
0
Note

In the first example, among 6 participants there were either zero winners and two awardees, or one winner and zero awardees.