apaz/codeforces-genesys huggingface dataset:
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 2.5 seconds
Memory limit: 256.0 MB

# Problem
The rules of Sith Tournament are well known to everyone. n Sith take part in the Tournament. The Tournament starts with the random choice of two Sith who will fight in the first battle. As one of them loses, his place is taken by the next randomly chosen Sith who didn't fight before. Does it need to be said that each battle in the Sith Tournament ends with a death of one of opponents? The Tournament ends when the only Sith remains alive.

Jedi Ivan accidentally appeared in the list of the participants in the Sith Tournament. However, his skills in the Light Side of the Force are so strong so he can influence the choice of participants either who start the Tournament or who take the loser's place after each battle. Of course, he won't miss his chance to take advantage of it. Help him to calculate the probability of his victory.

## Input Format
The first line contains a single integer n (1 ≤ n ≤ 18) — the number of participants of the Sith Tournament.

Each of the next n lines contains n real numbers, which form a matrix pij (0 ≤ pij ≤ 1). Each its element pij is the probability that the i-th participant defeats the j-th in a duel.

The elements on the main diagonal pii are equal to zero. For all different i, j the equality pij + pji = 1 holds. All probabilities are given with no more than six decimal places.

Jedi Ivan is the number 1 in the list of the participants.

## Output Format
Output a real number — the probability that Jedi Ivan will stay alive after the Tournament. Absolute or relative error of the answer must not exceed 10 - 6.

## Examples
```input
3
0.0 0.5 0.8
0.5 0.0 0.4
0.2 0.6 0.0
```
```output
0.680000000000000
```

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 4.0 seconds
Memory limit: 256.0 MB

# Problem
Lena is a programmer. She got a task to solve at work.

There is an empty set of pairs of integers and n queries to process. Each query is one of three types:

1. Add a pair (a, b) to the set.
2. Remove a pair added in the query number i. All queries are numbered with integers from 1 to n.
3. For a given integer q find the maximal value x·q + y over all pairs (x, y) from the set.

Help Lena to process the queries.

## Input Format
The first line of input contains integer n (1 ≤ n ≤ 3·105) — the number of queries.

Each of the next n lines starts with integer t (1 ≤ t ≤ 3) — the type of the query.

A pair of integers a and b ( - 109 ≤ a, b ≤ 109) follows in the query of the first type.

An integer i (1 ≤ i ≤ n) follows in the query of the second type. It is guaranteed that i is less than the number of the query, the query number i has the first type and the pair from the i-th query is not already removed.

An integer q ( - 109 ≤ q ≤ 109) follows in the query of the third type.

## Output Format
For the queries of the third type print on a separate line the desired maximal value of x·q + y.

If there are no pairs in the set print "EMPTY SET".

## Examples
```input
7
3 1
1 2 3
3 1
1 -1 100
3 1
2 4
3 1
```
```output
EMPTY SET
5
99
5
```

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Little Petya was given this problem for homework:

You are given function $$f(x) = (((x \mod p_{1}) \mod p_{2}) \mod p_{3}) \mod p_{4}$$ (here $$\bmod$$ represents the operation of taking the remainder). His task is to count the number of integers x in range [a;b] with property f(x) = x.

It is a pity that Petya forgot the order in which the remainders should be taken and wrote down only 4 numbers. Each of 24 possible orders of taking the remainder has equal probability of being chosen. For example, if Petya has numbers 1, 2, 3, 4 then he can take remainders in that order or first take remainder modulo 4, then modulo 2, 3, 1. There also are 22 other permutations of these numbers that represent orders in which remainder can be taken. In this problem 4 numbers wrote down by Petya will be pairwise distinct.

Now it is impossible for Petya to complete the task given by teacher but just for fun he decided to find the number of integers $$x \in [a;b]$$ with property that probability that f(x) = x is not less than 31.4159265352718281828459045%. In other words, Petya will pick up the number x if there exist at least 7 permutations of numbers p1, p2, p3, p4, for which f(x) = x.

## Input Format
First line of the input will contain 6 integers, separated by spaces: p1, p2, p3, p4, a, b (1 ≤ p1, p2, p3, p4 ≤ 1000, 0 ≤ a ≤ b ≤ 31415).

It is guaranteed that numbers p1, p2, p3, p4 will be pairwise distinct.

## Output Format
Output the number of integers in the given range that have the given property.

## Examples
```input
2 7 1 8 2 8
```
```output
0
```
-----
```input
20 30 40 50 0 100
```
```output
20
```
-----
```input
31 41 59 26 17 43
```
```output
9
```

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
It is well known that the planet suffers from the energy crisis. Little Petya doesn't like that and wants to save the world. For this purpose he needs every accumulator to contain the same amount of energy. Initially every accumulator has some amount of energy: the i-th accumulator has ai units of energy. Energy can be transferred from one accumulator to the other. Every time x units of energy are transferred (x is not necessarily an integer) k percent of it is lost. That is, if x units were transferred from one accumulator to the other, amount of energy in the first one decreased by x units and in other increased by $$x - \frac{xk}{100}$$ units.

Your task is to help Petya find what maximum equal amount of energy can be stored in each accumulator after the transfers.

## Input Format
First line of the input contains two integers n and k (1 ≤ n ≤ 10000, 0 ≤ k ≤ 99) — number of accumulators and the percent of energy that is lost during transfers.

Next line contains n integers a1, a2, ... , an — amounts of energy in the first, second, .., n-th accumulator respectively (0 ≤ ai ≤ 1000, 1 ≤ i ≤ n).

## Output Format
Output maximum possible amount of energy that can remain in each of accumulators after the transfers of energy.

The absolute or relative error in the answer should not exceed 10 - 6.

## Examples
```input
3 50
4 2 1
```
```output
2.000000000
```
-----
```input
2 90
1 11
```
```output
1.909090909
```

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
While swimming at the beach, Mike has accidentally dropped his cellphone into the water. There was no worry as he bought a cheap replacement phone with an old-fashioned keyboard. The keyboard has only ten digital equal-sized keys, located in the following way:

$$\begin{array}{ccc}
1 & 2 & 3 \\
4 & 5 & 6 \\
7 & 8 & 9 \\
0 &
\end{array}$$

Together with his old phone, he lost all his contacts and now he can only remember the way his fingers moved when he put some number in. One can formally consider finger movements as a sequence of vectors connecting centers of keys pressed consecutively to put in a number. For example, the finger movements for number "586" are the same as finger movements for number "253":

Mike has already put in a number by his "finger memory" and started calling it, so he is now worrying, can he be sure that he is calling the correct number? In other words, is there any other number, that has the same finger movements?

## Input Format
The first line of the input contains the only integer n (1 ≤ n ≤ 9) — the number of digits in the phone number that Mike put in.

The second line contains the string consisting of n digits (characters from '0' to '9') representing the number that Mike put in.

## Output Format
If there is no other phone number with the same finger movements and Mike can be sure he is calling the correct number, print "YES" (without quotes) in the only line.

Otherwise print "NO" (without quotes) in the first line.

## Examples
```input
3
586
```
```output
NO
```
-----
```input
2
09
```
```output
NO
```
-----
```input
9
123456789
```
```output
YES
```
-----
```input
3
911
```
```output
YES
```

## Note
You can find the picture clarifying the first sample case in the statement above.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
According to rules of the Berland fashion, a jacket should be fastened by all the buttons except only one, but not necessarily it should be the last one. Also if the jacket has only one button, it should be fastened, so the jacket will not swinging open.

You are given a jacket with n buttons. Determine if it is fastened in a right way.

## Input Format
The first line contains integer n (1 ≤ n ≤ 1000) — the number of buttons on the jacket.

The second line contains n integers ai (0 ≤ ai ≤ 1). The number ai = 0 if the i-th button is not fastened. Otherwise ai = 1.

## Output Format
In the only line print the word "YES" if the jacket is fastened in a right way. Otherwise print the word "NO".

## Examples
```input
3
1 0 1
```
```output
YES
```
-----
```input
3
1 0 0
```
```output
NO
```

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Let's call a string "s-palindrome" if it is symmetric about the middle of the string. For example, the string "oHo" is "s-palindrome", but the string "aa" is not. The string "aa" is not "s-palindrome", because the second half of it is not a mirror reflection of the first half.

English alphabet

You are given a string s. Check if the string is "s-palindrome".

## Input Format
The only line contains the string s (1 ≤ |s| ≤ 1000) which consists of only English letters.

## Output Format
Print "TAK" if the string s is "s-palindrome" and "NIE" otherwise.

## Examples
```input
oXoxoXo
```
```output
TAK
```
-----
```input
bod
```
```output
TAK
```
-----
```input
ER
```
```output
NIE
```

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given a positive decimal number x.

Your task is to convert it to the "simple exponential notation".

Let x = a·10b, where 1 ≤ a < 10, then in general case the "simple exponential notation" looks like "aEb". If b equals to zero, the part "Eb" should be skipped. If a is an integer, it should be written without decimal point. Also there should not be extra zeroes in a and b.

## Input Format
The only line contains the positive decimal number x. The length of the line will not exceed 106. Note that you are given too large number, so you can't use standard built-in data types "float", "double" and other.

## Output Format
Print the only line — the "simple exponential notation" of the given number x.

## Examples
```input
16
```
```output
1.6E1
```
-----
```input
01.23400
```
```output
1.234
```
-----
```input
.100
```
```output
1E-1
```
-----
```input
100.
```
```output
1E2
```

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 5.0 seconds
Memory limit: 256.0 MB

# Problem
You are given a permutation of the numbers 1, 2, ..., n and m pairs of positions (aj, bj).

At each step you can choose a pair from the given positions and swap the numbers in that positions. What is the lexicographically maximal permutation one can get?

Let p and q be two permutations of the numbers 1, 2, ..., n. p is lexicographically smaller than the q if a number 1 ≤ i ≤ n exists, so pk = qk for 1 ≤ k < i and pi < qi.

## Input Format
The first line contains two integers n and m (1 ≤ n, m ≤ 106) — the length of the permutation p and the number of pairs of positions.

The second line contains n distinct integers pi (1 ≤ pi ≤ n) — the elements of the permutation p.

Each of the last m lines contains two integers (aj, bj) (1 ≤ aj, bj ≤ n) — the pairs of positions to swap. Note that you are given a positions, not the values to swap.

## Output Format
Print the only line with n distinct integers p'i (1 ≤ p'i ≤ n) — the lexicographically maximal permutation one can get.

## Examples
```input
9 6
1 2 3 4 5 6 7 8 9
1 4
4 7
2 5
5 8
3 6
6 9
```
```output
7 8 9 4 5 6 1 2 3
```

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Fangy collects cookies. Once he decided to take a box and put cookies into it in some way. If we take a square k × k in size, divided into blocks 1 × 1 in size and paint there the main diagonal together with cells, which lie above it, then the painted area will be equal to the area occupied by one cookie k in size. Fangy also has a box with a square base 2n × 2n, divided into blocks 1 × 1 in size. In a box the cookies should not overlap, and they should not be turned over or rotated. See cookies of sizes 2 and 4 respectively on the figure:

To stack the cookies the little walrus uses the following algorithm. He takes out of the repository the largest cookie which can fit in some place in the box and puts it there. Everything could be perfect but alas, in the repository the little walrus has infinitely many cookies of size 2 and larger, and there are no cookies of size 1, therefore, empty cells will remain in the box. Fangy wants to know how many empty cells will be left in the end.

## Input Format
The first line contains a single integer n (0 ≤ n ≤ 1000).

## Output Format
Print the single number, equal to the number of empty cells in the box. The answer should be printed modulo 106 + 3.

## Examples
```input
3
```
```output
9
```

## Note
If the box possesses the base of 23 × 23 (as in the example), then the cookies will be put there in the following manner:

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.5 seconds
Memory limit: 256.0 MB

# Problem
In Walrusland public transport tickets are characterized by two integers: by the number of the series and by the number of the ticket in the series. Let the series number be represented by a and the ticket number — by b, then a ticket is described by the ordered pair of numbers (a, b).

The walruses believe that a ticket is lucky if a * b = rev(a) * rev(b). The function rev(x) reverses a number written in the decimal system, at that the leading zeroes disappear. For example, rev(12343) = 34321, rev(1200) = 21.

The Public Transport Management Committee wants to release x series, each containing y tickets, so that at least w lucky tickets were released and the total number of released tickets (x * y) were minimum. The series are numbered from 1 to x inclusive. The tickets in each series are numbered from 1 to y inclusive. The Transport Committee cannot release more than maxx series and more than maxy tickets in one series.

## Input Format
The first line contains three integers maxx, maxy, w (1 ≤ maxx, maxy ≤ 105, 1 ≤ w ≤ 107).

## Output Format
Print on a single line two space-separated numbers, the x and the y. If there are several possible variants, print any of them. If such x and y do not exist, print a single number  - 1.

## Examples
```input
2 2 1
```
```output
1 1
```
-----
```input
132 10 35
```
```output
7 5
```
-----
```input
5 18 1000
```
```output
-1
```
-----
```input
48 132 235
```
```output
22 111
```

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Once a walrus professor Plato asked his programming students to perform the following practical task.

The students had to implement such a data structure that would support a convex hull on some set of points S. The input to the program had q queries of two types:

1. Add a point with coordinates (x, y) into the set S. Note that in this case the convex hull of S could have changed, and could have remained the same.

2. Say whether a point with coordinates (x, y) belongs to an area limited by the convex hull, including the border.

All the students coped with the task. What about you?

## Input Format
The first line contains an integer q (4 ≤ q ≤ 105).

Then follow q lines in the following way: "t x y", where t is the query type (1 or 2), and (x, y) are the coordinates of the point ( - 106 ≤ x, y ≤ 106, x and y are integers).

There is at least one query of type 2.

It is guaranteed that the three queries of the first type follow first and the points given in the queries form a non-degenerative triangle. Also all the points added in S are distinct.

## Output Format
For each query of the second type print one string containing "YES", if the point lies inside the convex hull or on its border. Otherwise, print "NO".

## Examples
```input
8
1 0 0
1 2 0
1 2 2
2 1 0
1 0 2
2 1 1
2 2 1
2 20 -1
```
```output
YES
YES
YES
NO
```

Now solve the problem and return the code.