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 c++17.

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:
```cpp
<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 c++17.

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:
```cpp
<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 c++17.

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:
```cpp
<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 c++17.

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:
```cpp
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given a sequence $$$a_1, a_2, \dots, a_n$$$ consisting of $$$n$$$ integers.

You can choose any non-negative integer $$$D$$$ (i.e. $$$D \ge 0$$$), and for each $$$a_i$$$ you can:

- add $$$D$$$ (only once), i. e. perform $$$a_i := a_i + D$$$, or
- subtract $$$D$$$ (only once), i. e. perform $$$a_i := a_i - D$$$, or
- leave the value of $$$a_i$$$ unchanged.

It is possible that after an operation the value $$$a_i$$$ becomes negative.

Your goal is to choose such minimum non-negative integer $$$D$$$ and perform changes in such a way, that all $$$a_i$$$ are equal (i.e. $$$a_1=a_2=\dots=a_n$$$).

Print the required $$$D$$$ or, if it is impossible to choose such value $$$D$$$, print -1.

For example, for array $$$[2, 8]$$$ the value $$$D=3$$$ is minimum possible because you can obtain the array $$$[5, 5]$$$ if you will add $$$D$$$ to $$$2$$$ and subtract $$$D$$$ from $$$8$$$. And for array $$$[1, 4, 7, 7]$$$ the value $$$D=3$$$ is also minimum possible. You can add it to $$$1$$$ and subtract it from $$$7$$$ and obtain the array $$$[4, 4, 4, 4]$$$.

## Input Format
The first line of the input contains one integer $$$n$$$ ($$$1 \le n \le 100$$$) — the number of elements in $$$a$$$.

The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 100$$$) — the sequence $$$a$$$.

## Output Format
Print one integer — the minimum non-negative integer value $$$D$$$ such that if you add this value to some $$$a_i$$$, subtract this value from some $$$a_i$$$ and leave some $$$a_i$$$ without changes, all obtained values become equal.

If it is impossible to choose such value $$$D$$$, print -1.

## Examples
```input
6
1 4 4 7 4 1
```
```output
3
```
-----
```input
5
2 2 5 2 5
```
```output
3
```
-----
```input
4
1 3 3 7
```
```output
-1
```
-----
```input
2
2 8
```
```output
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 c++17.

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:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Polycarp has a cat and his cat is a real gourmet! Dependent on a day of the week he eats certain type of food:

- on Mondays, Thursdays and Sundays he eats fish food;
- on Tuesdays and Saturdays he eats rabbit stew;
- on other days of week he eats chicken stake.

Polycarp plans to go on a trip and already packed his backpack. His backpack contains:

- $$$a$$$ daily rations of fish food;
- $$$b$$$ daily rations of rabbit stew;
- $$$c$$$ daily rations of chicken stakes.

Polycarp has to choose such day of the week to start his trip that his cat can eat without additional food purchases as long as possible. Print the maximum number of days the cat can eat in a trip without additional food purchases, if Polycarp chooses the day of the week to start his trip optimally.

## Input Format
The first line of the input contains three positive integers $$$a$$$, $$$b$$$ and $$$c$$$ ($$$1 \le a, b, c \le 7\cdot10^8$$$) — the number of daily rations of fish food, rabbit stew and chicken stakes in Polycarps backpack correspondingly.

## Output Format
Print the maximum number of days the cat can eat in a trip without additional food purchases, if Polycarp chooses the day of the week to start his trip optimally.

## Examples
```input
2 1 1
```
```output
4
```
-----
```input
3 2 2
```
```output
7
```
-----
```input
1 100 1
```
```output
3
```
-----
```input
30 20 10
```
```output
39
```

## Note
In the first example the best day for start of the trip is Sunday. In this case, during Sunday and Monday the cat will eat fish food, during Tuesday — rabbit stew and during Wednesday — chicken stake. So, after four days of the trip all food will be eaten.

In the second example Polycarp can start his trip in any day of the week. In any case there are food supplies only for one week in Polycarps backpack.

In the third example Polycarp can start his trip in any day, excluding Wednesday, Saturday and Sunday. In this case, the cat will eat three different dishes in three days. Nevertheless that after three days of a trip there will be $$$99$$$ portions of rabbit stew in a backpack, can cannot eat anything in fourth day of a trip.

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 c++17.

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:
```cpp
<your code here>
```

Execution time limit: 4.0 seconds
Memory limit: 1024.0 MB

# Problem
You are given an array $$$a$$$ consisting of $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$.

Your problem is to find such pair of indices $$$i, j$$$ ($$$1 \le i < j \le n$$$) that $$$lcm(a_i, a_j)$$$ is minimum possible.

$$$lcm(x, y)$$$ is the least common multiple of $$$x$$$ and $$$y$$$ (minimum positive number such that both $$$x$$$ and $$$y$$$ are divisors of this number).

## Input Format
The first line of the input contains one integer $$$n$$$ ($$$2 \le n \le 10^6$$$) — the number of elements in $$$a$$$.

The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^7$$$), where $$$a_i$$$ is the $$$i$$$-th element of $$$a$$$.

## Output Format
Print two integers $$$i$$$ and $$$j$$$ ($$$1 \le i < j \le n$$$) such that the value of $$$lcm(a_i, a_j)$$$ is minimum among all valid pairs $$$i, j$$$. If there are multiple answers, you can print any.

## Examples
```input
5
2 4 8 3 6
```
```output
1 2
```
-----
```input
5
5 2 11 3 7
```
```output
2 4
```
-----
```input
6
2 5 10 1 10 2
```
```output
1 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 c++17.

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:
```cpp
<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 c++17.

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:
```cpp
<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 c++17.

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:
```cpp
<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.
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 c++17.

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:
```cpp
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
At Moscow Workshops ICPC team gets a balloon for each problem they solved first. Team MSU Red Panda got so many balloons that they didn't know how to spend them. So they came up with a problem with them.

There are several balloons, not more than $$$10^6$$$ in total, each one is colored in one of $$$k$$$ colors. We can perform the following operation: choose $$$k-1$$$ balloons such that they are of $$$k-1$$$ different colors, and recolor them all into remaining color. We can perform this operation any finite number of times (for example, we can only perform the operation if there are at least $$$k-1$$$ different colors among current balls).

How many different balloon configurations can we get? Only number of balloons of each color matters, configurations differing only by the order of balloons are counted as equal. As this number can be very large, output it modulo $$$998244353$$$.

## Input Format
The first line contains a single integer $$$k$$$ ($$$2 \le k \le 10^5$$$) —the number of colors.

The second line contains $$$k$$$ integers $$$a_1, a_2, \ldots, a_k$$$ ($$$0 \le a_i$$$) —initial configuration of balloons. $$$a_i$$$ is number of balloons of color $$$i$$$. The total number of balloons doesn't exceed $$$10^6$$$. In other words,

$$$a_1 + a_2 + a_3 + \ldots + a_k \le 10^6$$$.

## Output Format
Output number of possible configurations modulo $$$998244353$$$.

## Examples
```input
3
0 1 2
```
```output
3
```
-----
```input
4
1 1 1 1
```
```output
5
```
-----
```input
5
0 0 1 2 3
```
```output
1
```
-----
```input
3
2 2 8
```
```output
31
```

## Note
In the first example, there are $$$3$$$ configurations we can get: $$$[0, 1, 2]$$$, $$$[2, 0, 1]$$$, $$$[1, 2, 0]$$$.

In the second example, we can apply the operation not more than once, and possible configurations are: $$$[1, 1, 1, 1]$$$, $$$[0, 0, 0, 4]$$$, $$$[0, 0, 4, 0]$$$, $$$[0, 4, 0, 0]$$$, $$$[4, 0, 0, 0]$$$.

In the third example, we can't apply any operations, so the only achievable configuration is the starting one.

Now solve the problem and return the code.