ICPC Central Russia Regional Contest, 2024
A. Pyramidal paths
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Recently, in a class on discrete mathematics, student Sasha learned about pyramidal Hamiltonian paths. A Hamiltonian path is a path in a graph that passes through each vertex exactly once. A distinctive property of pyramidal Hamiltonian paths is that the vertex numbers in them either go first in ascending order of vertex numbers, and then in descending order of numbers, or first the numbers go in descending order of vertex numbers, and then in ascending order of numbers, and the intervals of ascending and descending must contain at least two elements (in this case, the intervals of ascending and descending may have a common element).

Input

The first line contains the number $$$n$$$ $$$(3 \le n \le 10^5)$$$ – the number of vertices in the Hamiltonian path.

The second line contains $$$n$$$ pairs of different numbers $$$a_i$$$ $$$(1 \le a_i \le n)$$$ – enumeration of the vertices of the path.

Output

In a single line, print "YES" (without quotes) if the specified Hamiltonian path is pyramidal, and "NO" otherwise.

Examples
Input
5
4 3 1 2 5
Output
YES
Input
3
1 3 2
Output
YES
Input
6
4 5 6 1 2 3
Output
NO
Input
5
1 2 3 4 5
Output
NO
Note

In the second test example, the path is divided into 2 intervals: (1, 3) and (3, 2).

B. Language for machines
time limit per test
0.25 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Preprocessing of one of the languages designed for equipment management consists of the following steps:

  1. Deleting empty lines. A line is considered empty if it contains only whitespace characters.
  2. Concatenating lines with a line break character at the end. The line break character is the dollar sign $, which can be followed by any number of whitespace characters. Concatenating is performed as follows: characters starting with the dollar sign and followed by whitespace characters to the end of the line (including the line feed itself) are excluded from the character stream.
  3. Deleting lines with comments. The language has only one-line comments. Comment lines start with a double dollar sign: $$, followed by at least one non-whitespace character. From the beginning of the line to the double dollar sign $$, only whitespace characters are allowed – the presence of other characters in front of it means that this is not a comment. The comment continues to the end of the line, and cannot be moved to the next one using the line break character. The entire comment line is deleted, including the leading whitespace characters (if any).

Spaces (code 32) and tabs (code 9) are considered whitespace characters in the language.

The program always ends with an empty line.

The conversions are carried out in the specified order:

  • The first point applies to the entire input stream – after it, there are no empty lines left in the stream.
  • The second point applies to all lines of the stream, taking into account that the initial line involved in the concatenating cannot be a comment.
  • For the resulting stream, the third point is executed.

Write a program that performs preprocessing of the described type.

Input

Input contains of program consisting of at least one non-empty program line (not a comment). The program can contain only ASCII characters with codes from 32 to 127, tabs (code 9), plus line feeds in the form of a combination of characters with codes 13(CR) and 10 (LF) in the specified order.

The size of the input program should not exceed 64 KB.

Output

Output a program containing at least one non-empty line, converted according to the above rules.

Examples
Input
EXAMPLE PROGRAM

Output
EXAMPLE PROGRAM
Input

EXAMPLE $
PROGRAM

Output
EXAMPLE PROGRAM
Input
 $$ COMMENT 
EXAMPLE

Output
EXAMPLE

C. Unsuccessful pseudo-random
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Hacker Kirill decided to develop a new random number generator. To do this, he took two large numbers $$$ n $$$ and $$$ m $$$, turned them into powers of two, added them up, and raised the resulting amount to a small power of $$$ k $$$, and got some number $$$ r = (2^n + 2^m)^k $$$. Random numbers were supposed to be cut from the binary notation of the number $$$ r $$$.

When Kirill posted his ideas on the forum, one of his colleagues said that the numbers obtained would be too non-random, pointing out that even just the number of ones in the binary representation in the number $$$ r $$$ is too predictable.

Help Kirill verify his colleague's statement. Write a program that uses the numbers $$$ n $$$, $$$ m $$$ and $$$ k $$$ to determine the number of ones in the binary representation of the number $$$ r = (2^n + 2^m)^k $$$.

Input

The single line contains 3 integers $$$ n (0 \leq n \leq 10^9) $$$, $$$ m (0 \leq m \leq 10^9) $$$ and $$$ k (0 \leq k \leq 100) $$$, separated by a space.

Output

In a single line, print a number – the amount of ones in the binary representation of the number $$$ r = (2^n + 2^m)^k $$$.

Example
Input
3 1 3
Output
6

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

To restore the elephant population in an African country, it was proposed that a specialized farm be created. A $$$n\times m$$$ kilometers section of savannah was allocated for the farm. The number of an elephant herd is such that in a day it eats vegetation on 1 square kilometer area, after which it should be moved to another place.

To optimize the process, the entire farm was divided into square plots with a side of 1 km, fenced. It was decided that the relocation of the herd would be carried out only once a day and only to the neighboring plot, which has a common side with the current one.

It was found that to maintain the most natural feeding process, elephants should eat the same grass for $$$ k $$$ days in a row. Each plot of the future grassland will be sown with one type of grass, and a total of $$$ p $$$ of grass varieties will be used.

To restore vegetation between herd visits as much as possible, it was proposed to create a cyclic route in such a way that it:

  • was as long as possible;
  • crossed only the vertical or horizontal boundaries of the plots;
  • did not contain self-intersections;
  • consisted of $$$ p $$$ segments sown with the same grass, with $$$ k $$$ plots in each.

Write a program that, using the given numbers $$$ n $$$, $$$ m $$$, $$$ k $$$ and $$$ p $$$, creates a route of the elephant herd, or report that there is no such solution.

Input

Input contains of four integers: $$$n ~ (1 \leq n\leq 100)$$$, $$$m ~ (1 \leq m\leq 100)$$$, $$$k$$$ and $$$ p $$$ $$$( k, p \gt 0,~ 2 \lt k\times p \leq n \times m )$$$ separated by spaces.

Output

The first line of the output should contain the word "YES" (without quotes) if a solution exists, and the word "NO" otherwise.

If a solution exists, then output a block of $$$n$$$ lines.

The block describes the route of the herd. Each line consists of $$$m$$$ different characters:

  • "."(dot) if this section is not visited;
  • "-"(minus) if the herd route crosses the left and right boundaries of the site;
  • "|"(vertical line) if the herd route crosses the upper and lower boundaries of the site;
  • "L"(capital Latin L) if the herd route crosses the upper and right boundaries of the site;
  • "r"(lowercase Latin r) if the herd route crosses the lower and right boundaries of the site;
  • "J"(Latin capital J) if the herd route crosses the left and upper boundaries of the site;
  • "7"(number 7) if the herd route crosses the left and lower boundaries of the site.

If there are multiple solutions, output any of them.

Examples
Input
3 3 2 4
Output
YES
r-7
|rJ
LJ.
Input
3 3 3 3
Output
NO

E. Nika and turnip
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Nika likes the fairy tale about the turnip. Everyone knows the fairy tale about the turnip, where they could pull it out of the ground with a common effort. A grandfather pulled a turnip, a grandmother pulled the grandfather, a granddaughter pulled the grandmother, Zhuchka pulled the granddaughter, a cat pulled Zhuchka, and a mouse pulled the cat. Nika is intrigued by the question: "Is the mouse really that strong?"

You know each of the $$$n$$$ helpers. An indicator of the strength of the $$$i$$$ helper is equal to $$$a_i$$$. Nika knows for sure that to pull out a turnip, you need to apply a minimum of $$$x$$$ force. The helpers can be swapped in any way in the row. When the helpers start pulling the turnip, their total strength equals $$$\displaystyle\sum_{i=1}^n\dfrac{b_i}{i}$$$, where $$$i$$$ is the number of the helper in the row (the first one stands furthest from the turnip, $$$n$$$ is holding onto the turnip), $$$b_i$$$ is his strength.

Help Nika determine if the helpers can pull out the turnip.

Input

The first line contains two integers $$$n$$$, $$$x$$$ $$$(1 \leq n \leq 1000, 1 \leq x \leq 10^{12})$$$  — the number of helpers and the total force that needs to be applied to pull the turnip out.

The second line contains $$$n$$$ integers $$$a_i$$$ $$$(1 \leq a_i \leq 10^{12})$$$  — the power of each helper.

Output

In a single line, print "YES" (without quotes) if the turnip can be pulled out, otherwise "NO".

Examples
Input
5 8
5 4 3 2 1
Output
YES
Input
6 20
10 4 2 4 2 8
Output
NO
Input
6 16
10 4 2 4 2 8
Output
YES

F. Mobile Communication
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In a remote area, there are N villages where mobile communication is absent. At one point, a major mobile provider allocated funds for the construction of one or two base stations in this area. Each station must be built directly in one of the villages. It only remains to determine in which villages to install the stations as well as choose their coverage radii so that residents of all the villages can use mobile phones.

It is clear that the larger the coverage radius of the station, the more expensive it is and the more electricity it consumes. Therefore, the provider decided to choose the locations for the stations and their coverage radii in such a way that the sum of the squares of the radii is minimal.

Determine in which villages to install the stations and what their coverage radii R1 and R2 should be, so that the sum R12 + R22 is minimized and every village is within the coverage area of at least one station. If one station is installed, the coverage radius of the second one can be considered equal to zero.

All villages are small, so they can be considered points. If a station serves a single village (where it is installed), then consider its coverage radius equal to 1.

Input

The first line of input contains an integer N — the number of villages (2 ≤ N ≤ 500). The following N lines contain two integers in the range from 0 to 109 — the coordinates of the villages. It's guaranteed that no two pairs of coordinates coincide.

Output

Output the minimum value of R12 + R22, rounded to the nearest integer.

Examples
Input
4
0 1
1 0
4 1
5 3
Output
7
Input
3
0 0
1 0
2 0
Output
1
Input
3
0 0
5 0
0 1
Output
2
Note

In the first example, you can place the first station with a radius of in village 1 and the second station with a radius of in village 3.

In the second example, it is enough to take only one station with a radius of 1 and place it in village 2 — it will serve all three villages.

In the third example, you can place a station with a radius of 1 in village 1 and a second station with a radius of 1 in village 2.

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

In addition to binary trees on classes on discrete mathematics, Professor R. also talks about oriented trees. Let's define a directed tree. An oriented (directed) tree is an acyclic oriented graph in which only one vertex has a zero in-degree (no arcs lead into it), and all other vertices have a in-degree of 1 (there is exactly one arc leading into each of them). A vertex with a zero in-degree is called the root of the tree, vertices with a zero out-degree (from which no arc originates) are called terminal vertices or leaves. The figure below shows an example of an oriented tree.

After the class on oriented trees, the professor gave the students the following task as a home assignment.

Let's paint all the vertices of the oriented tree in some colors (denote by $$$c_i$$$ the color of the vertex with the number $$$i$$$). After that, for each vertex $$$i$$$ Professor wants to know what is the most frequent color in a subtree whose root is the vertex with the number $$$i$$$.

No matter how hard the students tried, they couldn't figure out how to solve this problem. Help them by writing a program that will answer all the queries made by Professor R.

Input

The first line contains the number $$$N$$$ $$$(1 \le N \le 2 \cdot 10^5)$$$ – the number of vertices in the tree.

The second line contains $$$N$$$ numbers $$$c_i$$$ separated by a space $$$(1 \le c_i \le 10^9)$$$ – the colors of the vertices, the $$$i$$$th number corresponds to the vertex with the number $$$i$$$.

The following $$$N - 1$$$ lines contain pairs of numbers $$$u$$$ and $$$v$$$ $$$(1 \le u, v \le N, u \ne v)$$$ describing the edges of the tree. The vertex $$$u$$$ corresponds to the beginning of the edge, $$$v$$$ corresponds to its end. It is guaranteed that the graph in the input data is an oriented tree. It is not guaranteed that vertex $$$1$$$ is the root of the tree.

Output

Output $$$N$$$ numbers, separated by a space, where the $$$i$$$th number is equal to the most frequent color in a subtree whose root is equal to $$$i$$$. If there are several required colors, you need to output the color with the lowest value.

Examples
Input
8
1 2 3 4 5 6 7 8
1 3
1 5
1 6
6 2
6 7
6 8
3 4
Output
1 2 3 4 5 2 7 8
Input
8
1 2 1 1 1 2 2 2
1 3
1 5
1 6
6 2
6 7
6 8
3 4
Output
1 2 1 1 1 2 2 2
Note

Trees in the input data correspond to the picture from the statement.

H. University ranking
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In addition to teaching at the university, Professor R. participates in programming competitions as a task creator. Today, Professor R. had a bright idea – he decided to make a rating list of the universities that participated in the quarterfinal competitions in sports programming held in the city of Cyberslavl. To calculate the rating, the professor came up with a formula:

$$$R = 4 \cdot R_0 + 3 \cdot R_1 + 2 \cdot R_2$$$,

where $$$R$$$ is the overall rating, $$$R_0$$$ is the rating of this year, $$$R_1$$$ is the rating of the previous year, $$$R_2$$$ is the rating from two years ago. The university's rating at the end of the year is calculated according to the formula:

$$$R_y = 10 \cdot k + 2 \cdot a + b + c$$$,

where $$$R_y$$$ is the university's rating for the year, $$$k$$$ is the number of tasks solved by the strongest university team in the quarterfinals (the team that solved the most problems is considered the strongest, if the number of solved tasks are equal, the team that took the highest place is considered the strongest), $$$a, b, c$$$ – bonus points for the places received by the first, second and third teams of the university in the quarterfinals (if there were no second and third teams, they add 0 points to the rating).

Bonus points for places in the quarterfinals are awarded as follows: 50th place earns the team 1 point, 49th – 2 points, etc. in increments of 1 to 11th place inclusive, which thus "costs" 40 points. Next, the 10th place earns 42 points, the 9th – 44, the 8th – 46, the 7th – 48, the 6th – 50, the 5th – 53, the 4th – 57, the 3rd – 62, the 2nd – 68 and, finally, the 1st – 80 points.

Before applying this formula to all universities, Professor R. decided to calculate the rating for the Cyberslavl State University. It turned out to be not so easy – every year many teams come from the university, and the professor does not want to look for them in the table. So he asks you to help him and write a program that, based on the results of the last three quarterfinals, helps to calculate the university's rating.

Input

The first line contains the number $$$N_0$$$ $$$(1 \le N_0 \le 20)$$$ – the number of teams of the Cyberslavl State University that participated in the quarterfinals this year.

This is followed by $$$N_0$$$ lines describing the results of the teams in the quarterfinals this year. The result of each team is set in the format $$$name~problems~place$$$, where $$$name$$$ is the name of the team (a line of no more than 50 characters in length, consisting of numbers, capital and lowercase Latin letters, as well as underscores), $$$ploblems$$$ $$$(0 \le problems \le 15)$$$ – the number of tasks solved by the team, $$$place$$$ $$$(1 \le place \le 100)$$$ – the place taken by the team.

The next line contains the number $$$N_1$$$ $$$(1 \le N_1 \le 20)$$$ – the number of teams of the Cyberslavl State University that participated in the quarterfinals last year.

This is followed by $$$N_1$$$ lines in a format similar to the results of the current year.

The next line contains the number $$$N_2$$$ $$$(1 \le N_2 \le 20)$$$ – the number of teams from the Cyberslavl State University that participated in the quarterfinals two years ago.

Then $$$N_2$$$ lines in a format similar to the results of the current year.

It is guaranteed that all the data is correct and the teams that took higher places solved no less problems than the teams that took lower places, and there were no teams that took the same place.

Output

In a single line, print a number – the rating of the Cyberslavl State University.

Examples
Input
7
O0 10 1
mmm 7 7
MAD_DOS 4 20
OsuzhdayCPlusPlus 4 18
zero_divisor 4 23
Lemon 5 12
3pixels 5 13
6
STACKMANS 6 11
xiaococka 6 7
MMM 8 1
Lemon 6 12
AmateraSU 6 8
Four_dimensional_cat 4 19
9
Yess_we_can 13 1
chill_owls 9 5
STACKmans 5 17
MPM 5 18
Cherniy_zhisny_vazhno 4 23
Four_dimensional_cat 6 14
HuRMa 7 9
Dead_Inside_Team 7 11
LigaDravena 9 4
Output
3190
Input
1
Adyghe_SU_1 3 73
2
Adyghe_SU_1 6 36
Adyghe_SU_2 3 65
1
Adyghe_SU_1 5 19
Output
618
Note

Consider the second example.

One team took part in the quarterfinals this year, it solved 3 problems and did not receive bonus points, hence $$$R_0 = 30$$$. In the quarterfinals last year, the best team solved 6 problems and took 36-th place, received 15 bonus points, hence $$$R_1 = 60 + 2 \cdot 15 = 90$$$. Two years ago one team that participated in the quarterfinals solved 5 problems and received 32 bonus points, hence $$$R_2 = 50 + 2 \cdot 32 = 114$$$. Total $$$R = 4 \cdot R_0 + 3 \cdot R_1 + 2 \cdot R_2 = 4 \cdot 30 + 3 \cdot 90 + 2 \cdot 114 = 618$$$.

I. Nicka and the goldfish
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Nika likes the tale of the goldfish. Nika decided that she could draw a goldfish herself. Nika drew each part of the goldfish in the form of polygons without self-intersections. The tail of a goldfish is connected to the body at a single vertex, and the head is connected to the body along one common segment.

Nika was able to number all the vertices, she has got $$$n$$$ of them, but calculating the size of each part of the goldfish turned out to be a difficult task for her. Help Nika calculate how many segments the goldfish's head, trunk and tail consist of.

Input

The first line contains an integer $$$n$$$ $$$(6\leq n \leq 10^5)$$$  — the number of vertices in the fish.

Next, $$$n+2$$$ lines are given, in which pairs of integers $$$a_i$$$, $$$b_i$$$ $$$(1 \leq a_i,~b_i \leq n)$$$ are specified  — the numbers of vertices connected by a segment.

It is guaranteed that the head, trunk and tail consist of at least three segments.

It is guaranteed that the head and tail do not have common vertices.

Output

In a single line, print three integers separated by a space – the number of segments in the head, trunk and tail of the goldfish, respectively.

Example
Input
11
1 2
1 4
2 3
4 3
9 10
11 10
11 9
5 7
7 9
4 6
6 8
8 10
4 5
Output
3 7 4
Note

The example goldfish looks like this:

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

Petya and Vasya got bored of playing with pebbles, and they decided to invent their own game. The Battleship was taken as a basis and was improved.

The new game is played on a $$$ 1 \times n $$$ checkered field. The cells of the field are numbered from 1 to $$$ n $$$ from left to right.

Petya hides a single ship with a length of $$$ k $$$ decks on the field.

Vasya tries to find the ship by guessing the numbers $$$ t $$$ and telling them to Petya. In response to the reported number $$$ t $$$, Petya calculates the number $$$ r $$$ – how many times the ship would have been hit if the cells $$$ t, 2t, 3t, ..., r \times t, ... $$$ had been shot. The results of the attempts are recorded in the protocol. Vasya can make $$$ c $$$ attempts and wins if he accurately determines the position of Petya's ship.

Write a program that, according to the protocol of the game finds the position of the ship, if such a position exists.

Input

The first line contains three integers $$$n$$$, $$$k$$$ ($$$1 \lt n \leq 1000, 0 \lt k \lt n$$$) and $$$c$$$ ($$$0\leq c \leq 100$$$). This is followed by $$$c$$$ lines containing pairs of numbers $$$t_i$$$ (step of the $$$i$$$th attempt, $$$0 \lt t_i \lt n$$$) and $$$r_i$$$ (result of the $$$i$$$th attempt, $$$0\leq r_i \leq k$$$).

Output

In a single line, print a number – the position of the ship, given by the number of its leftmost cell. If the position does not exist, print -1. If there are several valid positions, then print the leftmost one.

Examples
Input
16 5 3
2 3
3 1
5 1
Output
4
Input
16 5 3
2 3
3 1
15 1
Output
-1
Input
16 5 3
2 3
3 1
14 1
Output
10

K. Gray's numerical sequence
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

While reading an old algebra textbook, Professor R. came across interesting numerical sequences called Gray sequences. The first Gray sequence consists of the number $$$1$$$, the second Gray sequence consists of the numbers $$$1, 2, 1$$$, the third Gray sequence is $$$1, 2, 1, 3, 1, 2, 1$$$ etc., the Gray's sequence with a number $$$i$$$ consists of $$$(i - 1)$$$-th Gray sequence, the number $$$i$$$ and the newly written $$$(i - 1)$$$-th Gray sequence. The professor denoted by $$$f(n)$$$ the sum of the numbers in Gray's $$$n$$$-th sequence and asks you to write a program that finds the correct answer for a given $$$n$$$. Since this sum can be very large, he asks to calculate the remainder of dividing the sum by the number $$$10^9 + 9$$$.

Input

The single line contains the number $$$n$$$ $$$(1 \le n \le 10^{18})$$$ – the number of the Gray sequence.

Output

In a single line, output the number – the remainder of dividing $$$f(n)$$$ by $$$10^9 + 9$$$.

Examples
Input
1
Output
1
Input
2
Output
4
Input
1000
Output
829390959

L. Pills
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

This problem is interactive.

Professor R.'s brother, Dr. R., is a pharmacist who works in one of the pharmacies in Cyberslavl. Today, a batch of $$$N$$$ bottles of pills for memory strengthening came to his pharmacy, each bottle contains $$$N$$$ pills. However, trouble happened: it turned out that all the pills in one of the bottles were fake. It is known that each pill with a real medicine weighs $$$500$$$ milligrams, and each fake pill weighs $$$501$$$ milligrams. Dr. R. has accurate scales that show the total weight of the pills on them. Dr. R. wants to find the bottle with fake pills in one weighing. To make it easier, he numbered the bottles from $$$1$$$ to $$$N$$$, but he never figured out how to do one weighing correctly. The doctor tried to address this question to his brother, but he had left for a scientific conference and was unavailable. Therefore, Dr. R. asks you to help him to identify a bottle with fake pills.

Interaction

First, the number $$$N$$$ $$$(1 \le N \le 10^5)$$$ is given to your program as input – the number of bottles of pills.

After that, your program can make a request:

  1. In the first line, you need to print $$$K$$$ $$$(1 \le K \le N)$$$ – the number of bottles to open.
  2. In the following $$$K$$$ lines, you need to output to the output stream pairs of numbers $$$x~y$$$ $$$(1 \le x \le N, 1 \le y \le N)$$$, where $$$x$$$ is the number of the bottle, $$$y$$$ is the number of pills that are placed on the scale.

As a response to the request, you need to read the number – the total weight of the pills in milligrams, which the scales showed.

After making a request, you need to determine the number of the bottle with the fake pills. To do this, you need to output "$$$!~M$$$" to the output stream in a separate line, where $$$M$$$ is the number of the bottle with fake pills, according to your opinion.

If your program makes more than 1 request or sets an incorrect request (for example, requests a number of a bottle or a number of pills greater than $$$N$$$), it will receive any verdict other than "Accepted".

After printing a query do not forget to output end of line and flush the output. After the output of another request, be sure to use the stream cleanup functions so that part of your output does not remain in some buffer. For example, in C++ it is necessary to use the function "fflush(stdout)" or "cout.flush()", in Java and Kotlin the call "System.out.flush()" and "stdout.flush()" for Python.

Example
Input
1

501
Output
1
1 1

! 1

M. Playing with magnets
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Three wheels 1, 2 and 3 with rim lengths of $$$k$$$, $$$l$$$ and $$$m$$$ centimeters rotate freely on the axes. The wheels' axes are fixed on a straight beam from left to right so that wheel 1 comes into contact with wheel 2, and wheel 2 comes into contact with wheel 3. If you rotate wheel 1, it will transfer rotation to wheel 2, and then, in turn, to wheel 3.

Magnets of different strengths are fixed next to the wheel rims every centimeter. For simplicity, the strength of the magnets is denoted by integers from 1 (the weakest magnet) to $$$max(k, l, m) $$$ (the strongest). The magnets of the first wheel have a force of $$$1, 2, 3, ..., k$$$, of the second – $$$ 1, 2, 3, ..., l $$$, the third – $$$ 1, 2, 3, ..., m $$$. On each wheel, the magnets are arranged strictly in ascending order and counterclockwise direction (except for the strongest and weakest magnets standing side by side).

Initially, the wheels are positioned so that the weakest magnets (with a force of 1) are in the leftmost position. A magnet with a force of 200 (stronger than any other magnet on wheels) is fixed next to the rightmost point of wheel 3.

The first wheel starts rotating at a speed of 1 cm of rim per second clockwise. Accordingly, the second wheel rotates at the same speed, but counterclockwise. The third wheel rotates at the same speed, but again clockwise. An iron ball is fixed on the magnet 1 of the first wheel. During the rotation of the wheels, the ball can move from a weak magnet to a stronger one, but only at the points where the wheels connect, or from the rightmost position of the wheel 3 to the magnet with a force of 200.

Write a program that, based on the given numbers $$$k$$$, $$$l$$$ and $$$ m$$$ determines whether the ball will ever be on the magnet 200, and if it gets there, then how many seconds after the wheels start rotating.

Input

The input contains three integers $$$k$$$, $$$l$$$ and $$$m$$$($$$4\leq k,l,m\leq 100$$$, all $$$k, l, m$$$ – even), separated by spaces.

Output

Output the number of seconds from the start of rotation to the moment when the ball gets to the magnet 200, or -1, if it will never be on it.

Examples
Input
4 6 8
Output
9
Input
4 8 4
Output
-1
Input
4 4 4
Output
-1
Note
Example for wheels, sizes 4, 6 and 8.

N. Auto-completion
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

The creators of the operating system "X" relied on working in the terminal and included the SuperShell shell in the distribution package.

While working in SuperShell, one can enter the name of the necessary file character by character or use Tab for automatic completion.

Pressing the Tab key works as follows. Let's consider a subset of directory file names whose prefix matches the line already written in SuperShell. As a result of pressing Tab, the written line will be expanded to the maximum length of the common prefix among the files in this subset.

Freddy — one of the developers "X" — tested the shell and, once in the directory with logs, wondered what the minimum number of characters would need to be typed on the keyboard to open the desired file. Pressing Tab is also considered entering a character.

Input

The first line contains the number $$$N$$$ ($$$1 \le N \le 2000$$$) — the number of files in the directory.

This is followed by $$$N$$$ lines, each contains the line $$$f_i$$$ ($$$1 \le i \le N$$$, $$$1 \le |f_i| \le 2000$$$), consisting of lowercase Latin letters — filenames in the directory. Moreover, the file Freddy needs is listed first.

Output

Output one number — the minimum number of keypresses that Freddy will need.

Example
Input
4
bacb
ab
baca
caa
Output
3
Note

To open the required file from the example, Freddy just needs to click: $$$b$$$ —Tab — $$$b$$$.