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: 3.0 seconds
Memory limit: 256.0 MB

# Problem
You are given a permutation $$$p$$$ of integers from $$$1$$$ to $$$n$$$, where $$$n$$$ is an even number.

Your goal is to sort the permutation. To do so, you can perform zero or more operations of the following type:

- take two indices $$$i$$$ and $$$j$$$ such that $$$2 \cdot |i - j| \geq n$$$ and swap $$$p_i$$$ and $$$p_j$$$.

There is no need to minimize the number of operations, however you should use no more than $$$5 \cdot n$$$ operations. One can show that it is always possible to do that.

## Input Format
The first line contains a single integer $$$n$$$ ($$$2 \leq n \leq 3 \cdot 10^5$$$, $$$n$$$ is even) — the length of the permutation.

The second line contains $$$n$$$ distinct integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$) — the given permutation.

## Output Format
On the first line print $$$m$$$ ($$$0 \le m \le 5 \cdot n$$$) — the number of swaps to perform.

Each of the following $$$m$$$ lines should contain integers $$$a_i, b_i$$$ ($$$1 \le a_i, b_i \le n$$$, $$$|a_i - b_i| \ge \frac{n}{2}$$$) — the indices that should be swapped in the corresponding swap.

Note that there is no need to minimize the number of operations. We can show that an answer always exists.

## Examples
```input
2
2 1
```
```output
1
1 2
```
-----
```input
4
3 4 1 2
```
```output
4
1 4
1 4
1 3
2 4
```
-----
```input
6
2 5 3 1 4 6
```
```output
3
1 5
2 5
1 4
```

## Note
In the first example, when one swap elements on positions $$$1$$$ and $$$2$$$, the array becomes sorted.

In the second example, pay attention that there is no need to minimize number of swaps.

In the third example, after swapping elements on positions $$$1$$$ and $$$5$$$ the array becomes: $$$[4, 5, 3, 1, 2, 6]$$$. After swapping elements on positions $$$2$$$ and $$$5$$$ the array becomes $$$[4, 2, 3, 1, 5, 6]$$$ and finally after swapping elements on positions $$$1$$$ and $$$4$$$ the array becomes sorted: $$$[1, 2, 3, 4, 5, 6]$$$.

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: 3.0 seconds
Memory limit: 256.0 MB

# Problem
You are given $$$n$$$ pairs of integers $$$(a_1, b_1), (a_2, b_2), \ldots, (a_n, b_n)$$$. All of the integers in the pairs are distinct and are in the range from $$$1$$$ to $$$2 \cdot n$$$ inclusive.

Let's call a sequence of integers $$$x_1, x_2, \ldots, x_{2k}$$$ good if either

- $$$x_1 < x_2 > x_3 < \ldots < x_{2k-2} > x_{2k-1} < x_{2k}$$$, or
- $$$x_1 > x_2 < x_3 > \ldots > x_{2k-2} < x_{2k-1} > x_{2k}$$$.

You need to choose a subset of distinct indices $$$i_1, i_2, \ldots, i_t$$$ and their order in a way that if you write down all numbers from the pairs in a single sequence (the sequence would be $$$a_{i_1}, b_{i_1}, a_{i_2}, b_{i_2}, \ldots, a_{i_t}, b_{i_t}$$$), this sequence is good.

What is the largest subset of indices you can choose? You also need to construct the corresponding index sequence $$$i_1, i_2, \ldots, i_t$$$.

## Input Format
The first line contains single integer $$$n$$$ ($$$2 \leq n \leq 3 \cdot 10^5$$$) — the number of pairs.

Each of the next $$$n$$$ lines contain two numbers — $$$a_i$$$ and $$$b_i$$$ ($$$1 \le a_i, b_i \le 2 \cdot n$$$) — the elements of the pairs.

It is guaranteed that all integers in the pairs are distinct, that is, every integer from $$$1$$$ to $$$2 \cdot n$$$ is mentioned exactly once.

## Output Format
In the first line print a single integer $$$t$$$ — the number of pairs in the answer.

Then print $$$t$$$ distinct integers $$$i_1, i_2, \ldots, i_t$$$ — the indexes of pairs in the corresponding order.

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

## Note
The final sequence in the first example is $$$1 < 7 > 3 < 5 > 2 < 10$$$.

The final sequence in the second example is $$$6 > 1 < 3 > 2 < 5 > 4$$$.

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
There are $$$n$$$ stones arranged on an axis. Initially the $$$i$$$-th stone is located at the coordinate $$$s_i$$$. There may be more than one stone in a single place.

You can perform zero or more operations of the following type:

- take two stones with indices $$$i$$$ and $$$j$$$ so that $$$s_i \leq s_j$$$, choose an integer $$$d$$$ ($$$0 \leq 2 \cdot d \leq s_j - s_i$$$), and replace the coordinate $$$s_i$$$ with $$$(s_i + d)$$$ and replace coordinate $$$s_j$$$ with $$$(s_j - d)$$$. In other words, draw stones closer to each other.

You want to move the stones so that they are located at positions $$$t_1, t_2, \ldots, t_n$$$. The order of the stones is not important — you just want for the multiset of the stones resulting positions to be the same as the multiset of $$$t_1, t_2, \ldots, t_n$$$.

Detect whether it is possible to move the stones this way, and if yes, construct a way to do so. You don't need to minimize the number of moves.

## Input Format
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) – the number of stones.

The second line contains integers $$$s_1, s_2, \ldots, s_n$$$ ($$$1 \le s_i \le 10^9$$$) — the initial positions of the stones.

The second line contains integers $$$t_1, t_2, \ldots, t_n$$$ ($$$1 \le t_i \le 10^9$$$) — the target positions of the stones.

## Output Format
If it is impossible to move the stones this way, print "NO".

Otherwise, on the first line print "YES", on the second line print the number of operations $$$m$$$ ($$$0 \le m \le 5 \cdot n$$$) required. You don't have to minimize the number of operations.

Then print $$$m$$$ lines, each containing integers $$$i, j, d$$$ ($$$1 \le i, j \le n$$$, $$$s_i \le s_j$$$, $$$0 \leq 2 \cdot d \leq s_j - s_i$$$), defining the operations.

One can show that if an answer exists, there is an answer requiring no more than $$$5 \cdot n$$$ operations.

## Examples
```input
5
2 2 7 4 9
5 4 5 5 5
```
```output
YES
4
4 3 1
2 3 1
2 5 2
1 5 2
```
-----
```input
3
1 5 10
3 5 7
```
```output
NO
```

## Note
Consider the first example.

- After the first move the locations of stones is $$$[2, 2, 6, 5, 9]$$$.
- After the second move the locations of stones is $$$[2, 3, 5, 5, 9]$$$.
- After the third move the locations of stones is $$$[2, 5, 5, 5, 7]$$$.
- After the last move the locations of stones is $$$[4, 5, 5, 5, 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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Welcome to Codeforces Stock Exchange! We're pretty limited now as we currently allow trading on one stock, Codeforces Ltd. We hope you'll still be able to make profit from the market!

In the morning, there are $$$n$$$ opportunities to buy shares. The $$$i$$$-th of them allows to buy as many shares as you want, each at the price of $$$s_i$$$ bourles.

In the evening, there are $$$m$$$ opportunities to sell shares. The $$$i$$$-th of them allows to sell as many shares as you want, each at the price of $$$b_i$$$ bourles. You can't sell more shares than you have.

It's morning now and you possess $$$r$$$ bourles and no shares.

What is the maximum number of bourles you can hold after the evening?

## Input Format
The first line of the input contains three integers $$$n, m, r$$$ ($$$1 \leq n \leq 30$$$, $$$1 \leq m \leq 30$$$, $$$1 \leq r \leq 1000$$$) — the number of ways to buy the shares on the market, the number of ways to sell the shares on the market, and the number of bourles you hold now.

The next line contains $$$n$$$ integers $$$s_1, s_2, \dots, s_n$$$ ($$$1 \leq s_i \leq 1000$$$); $$$s_i$$$ indicates the opportunity to buy shares at the price of $$$s_i$$$ bourles.

The following line contains $$$m$$$ integers $$$b_1, b_2, \dots, b_m$$$ ($$$1 \leq b_i \leq 1000$$$); $$$b_i$$$ indicates the opportunity to sell shares at the price of $$$b_i$$$ bourles.

## Output Format
Output a single integer — the maximum number of bourles you can hold after the evening.

## Examples
```input
3 4 11
4 2 5
4 4 5 4
```
```output
26
```
-----
```input
2 2 50
5 7
4 2
```
```output
50
```

## Note
In the first example test, you have $$$11$$$ bourles in the morning. It's optimal to buy $$$5$$$ shares of a stock at the price of $$$2$$$ bourles in the morning, and then to sell all of them at the price of $$$5$$$ bourles in the evening. It's easy to verify that you'll have $$$26$$$ bourles after the evening.

In the second example test, it's optimal not to take any action.

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
One day Alice was cleaning up her basement when she noticed something very curious: an infinite set of wooden pieces! Each piece was made of five square tiles, with four tiles adjacent to the fifth center tile:

Alice started wondering whether she could fill the board completely using the pieces she had found. Of course, each piece has to cover exactly five distinct cells of the board, no two pieces can overlap and every piece should fit in the board entirely, without some parts laying outside the board borders. The board however was too large for Alice to do the tiling by hand. Can you help determine if it's possible to fully tile the board?

## Input Format
The first line of the input contains a single integer $$$n$$$ ($$$3 \leq n \leq 50$$$) — the size of the board.

The following $$$n$$$ lines describe the board. The $$$i$$$-th line ($$$1 \leq i \leq n$$$) contains a single string of length $$$n$$$. Its $$$j$$$-th character ($$$1 \leq j \leq n$$$) is equal to "." if the cell in the $$$i$$$-th row and the $$$j$$$-th column is free; it is equal to "#" if it's occupied.

You can assume that the board contains at least one free cell.

## Output Format
Output YES if the board can be tiled by Alice's pieces, or NO otherwise. You can print each letter in any case (upper or lower).

## Examples
```input
3
#.#
...
#.#
```
```output
YES
```
-----
```input
4
##.#
#...
####
##.#
```
```output
NO
```
-----
```input
5
#.###
....#
#....
###.#
#####
```
```output
YES
```
-----
```input
5
#.###
....#
#....
....#
#..##
```
```output
NO
```

## Note
The following sketches show the example boards and their tilings if such tilings exist:

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
A telephone number is a sequence of exactly $$$11$$$ digits such that its first digit is 8.

Vasya and Petya are playing a game. Initially they have a string $$$s$$$ of length $$$n$$$ ($$$n$$$ is odd) consisting of digits. Vasya makes the first move, then players alternate turns. In one move the player must choose a character and erase it from the current string. For example, if the current string 1121, after the player's move it may be 112, 111 or 121. The game ends when the length of string $$$s$$$ becomes 11. If the resulting string is a telephone number, Vasya wins, otherwise Petya wins.

You have to determine if Vasya has a winning strategy (that is, if Vasya can win the game no matter which characters Petya chooses during his moves).

## Input Format
The first line contains one integer $$$n$$$ ($$$13 \le n < 10^5$$$, $$$n$$$ is odd) — the length of string $$$s$$$.

The second line contains the string $$$s$$$ ($$$|s| = n$$$) consisting only of decimal digits.

## Output Format
If Vasya has a strategy that guarantees him victory, print YES.

Otherwise print NO.

## Examples
```input
13
8380011223344
```
```output
YES
```
-----
```input
15
807345619350641
```
```output
NO
```

## Note
In the first example Vasya needs to erase the second character. Then Petya cannot erase a character from the remaining string 880011223344 so that it does not become a telephone number.

In the second example after Vasya's turn Petya can erase one character character 8. The resulting string can't be a telephone number, because there is no digit 8 at all.

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
In a very ancient country the following game was popular. Two people play the game. Initially first player writes a string s1, consisting of exactly nine digits and representing a number that does not exceed a. After that second player looks at s1 and writes a string s2, consisting of exactly nine digits and representing a number that does not exceed b. Here a and b are some given constants, s1 and s2 are chosen by the players. The strings are allowed to contain leading zeroes.

If a number obtained by the concatenation (joining together) of strings s1 and s2 is divisible by mod, then the second player wins. Otherwise the first player wins. You are given numbers a, b, mod. Your task is to determine who wins if both players play in the optimal manner. If the first player wins, you are also required to find the lexicographically minimum winning move.

## Input Format
The first line contains three integers a, b, mod (0 ≤ a, b ≤ 109, 1 ≤ mod ≤ 107).

## Output Format
If the first player wins, print "1" and the lexicographically minimum string s1 he has to write to win. If the second player wins, print the single number "2".

## Examples
```input
1 10 7
```
```output
2
```
-----
```input
4 0 9
```
```output
1 000000001
```

## Note
The lexical comparison of strings is performed by the < operator in modern programming languages. String x is lexicographically less than string y if exists such i (1 ≤ i ≤ 9), that xi < yi, and for any j (1 ≤ j < i) xj = yj. These strings always have length 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.5 seconds
Memory limit: 256.0 MB

# Problem
A tournament is a directed graph without self-loops in which every pair of vertexes is connected by exactly one directed edge. That is, for any two vertexes u and v (u ≠ v) exists either an edge going from u to v, or an edge from v to u.

You are given a tournament consisting of n vertexes. Your task is to find there a cycle of length three.

## Input Format
The first line contains an integer n (1 ≤ n ≤ 5000). Next n lines contain the adjacency matrix A of the graph (without spaces). Ai, j = 1 if the graph has an edge going from vertex i to vertex j, otherwise Ai, j = 0. Ai, j stands for the j-th character in the i-th line.

It is guaranteed that the given graph is a tournament, that is, Ai, i = 0, Ai, j ≠ Aj, i (1 ≤ i, j ≤ n, i ≠ j).

## Output Format
Print three distinct vertexes of the graph a1, a2, a3 (1 ≤ ai ≤ n), such that Aa1, a2 = Aa2, a3 = Aa3, a1 = 1, or "-1", if a cycle whose length equals three does not exist.

If there are several solutions, print any of them.

## Examples
```input
5
00100
10000
01001
11101
11000
```
```output
1 3 2
```
-----
```input
5
01111
00000
01000
01100
01110
```
```output
-1
```

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
Fedor runs for president of Byteland! In the debates, he will be asked how to solve Byteland's transport problem. It's a really hard problem because of Byteland's transport system is now a tree (connected graph without cycles). Fedor's team has found out in the ministry of transport of Byteland that there is money in the budget only for one additional road. In the debates, he is going to say that he will build this road as a way to maximize the number of distinct simple paths in the country. A simple path is a path which goes through every vertex no more than once. Two simple paths are named distinct if sets of their edges are distinct.

But Byteland's science is deteriorated, so Fedor's team hasn't succeeded to find any scientists to answer how many distinct simple paths they can achieve after adding exactly one edge on the transport system?

Help Fedor to solve it.

An edge can be added between vertices that are already connected, but it can't be a loop.

In this problem, we consider only simple paths of length at least two.

## Input Format
The first line contains one integer $$$n$$$ ($$$2 \leq n \leq 500\ 000$$$) — number of vertices in Byteland's transport system.

Each of the following $$$n - 1$$$ lines contains two integers $$$v_i$$$ and $$$u_i$$$ ($$$1 \leq v_i, u_i \leq n$$$). It's guaranteed that the graph is tree.

## Output Format
Print exactly one integer — a maximal number of simple paths that can be achieved after adding one edge.

## Examples
```input
2
1 2
```
```output
2
```
-----
```input
4
1 2
1 3
1 4
```
```output
11
```
-----
```input
6
1 2
1 3
3 4
3 5
4 6
```
```output
29
```

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
You are given $$$n$$$ numbers $$$a_1, a_2, \dots, a_n$$$. In one operation we can add to any one of those numbers a nonnegative integer power of $$$2$$$.

What is the smallest number of operations we need to perform to make all $$$n$$$ numbers equal? It can be proved that under given constraints it doesn't exceed $$$10^{18}$$$.

## Input Format
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^{17}$$$).

## Output Format
Output exactly one integer — the smallest number of operations we need to perform to make all $$$n$$$ numbers equal.

## Examples
```input
4
228 228 228 228
```
```output
0
```
-----
```input
3
2 2 8
```
```output
3
```

## Note
In the first example, all numbers are already equal. So the needed number of operation is $$$0$$$.

In the second example, we can apply the operation $$$3$$$ times: add $$$8$$$ to first $$$2$$$, add $$$8$$$ to second $$$2$$$, add $$$2$$$ to $$$8$$$, making all numbers equal to $$$10$$$. It can be proved that we can't make all numbers equal in less than $$$3$$$ operations.

Now solve the problem and return the code.