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

# Problem
ZS the Coder and Chris the Baboon arrived at the entrance of Udayland. There is a n × n magic grid on the entrance which is filled with integers. Chris noticed that exactly one of the cells in the grid is empty, and to enter Udayland, they need to fill a positive integer into the empty cell.

Chris tried filling in random numbers but it didn't work. ZS the Coder realizes that they need to fill in a positive integer such that the numbers in the grid form a magic square. This means that he has to fill in a positive integer so that the sum of the numbers in each row of the grid ($$\sum_{r,i}a_{r,i}$$), each column of the grid ($$\sum_{i,c}a_{i,c}$$), and the two long diagonals of the grid (the main diagonal — $$\sum_{i}a_{i,i}$$ and the secondary diagonal — $$\sum_{i}a_{i,n-i+1}$$) are equal.

Chris doesn't know what number to fill in. Can you help Chris find the correct positive integer to fill in or determine that it is impossible?

## Input Format
The first line of the input contains a single integer n (1 ≤ n ≤ 500) — the number of rows and columns of the magic grid.

n lines follow, each of them contains n integers. The j-th number in the i-th of them denotes ai, j (1 ≤ ai, j ≤ 109 or ai, j = 0), the number in the i-th row and j-th column of the magic grid. If the corresponding cell is empty, ai, j will be equal to 0. Otherwise, ai, j is positive.

It is guaranteed that there is exactly one pair of integers i, j (1 ≤ i, j ≤ n) such that ai, j = 0.

## Output Format
Output a single integer, the positive integer x (1 ≤ x ≤ 1018) that should be filled in the empty cell so that the whole grid becomes a magic square. If such positive integer x does not exist, output  - 1 instead.

If there are multiple solutions, you may print any of them.

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

## Note
In the first sample case, we can fill in 9 into the empty cell to make the resulting grid a magic square. Indeed,

The sum of numbers in each row is:

4 + 9 + 2 = 3 + 5 + 7 = 8 + 1 + 6 = 15.

The sum of numbers in each column is:

4 + 3 + 8 = 9 + 5 + 1 = 2 + 7 + 6 = 15.

The sum of numbers in the two diagonals is:

4 + 5 + 6 = 2 + 5 + 8 = 15.

In the third sample case, it is impossible to fill a number in the empty square such that the resulting grid is a magic square.

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
ZS the Coder has recently found an interesting concept called the Birthday Paradox. It states that given a random set of 23 people, there is around 50% chance that some two of them share the same birthday. ZS the Coder finds this very interesting, and decides to test this with the inhabitants of Udayland.

In Udayland, there are 2n days in a year. ZS the Coder wants to interview k people from Udayland, each of them has birthday in one of 2n days (each day with equal probability). He is interested in the probability of at least two of them have the birthday at the same day.

ZS the Coder knows that the answer can be written as an irreducible fraction $$\frac{\overline{A}}{\overline{B}}$$. He wants to find the values of A and B (he does not like to deal with floating point numbers). Can you help him?

## Input Format
The first and only line of the input contains two integers n and k (1 ≤ n ≤ 1018, 2 ≤ k ≤ 1018), meaning that there are 2n days in a year and that ZS the Coder wants to interview exactly k people.

## Output Format
If the probability of at least two k people having the same birthday in 2n days long year equals $$\frac{\overline{A}}{\overline{B}}$$ (A ≥ 0, B ≥ 1, $$\gcd(A,B)=1$$), print the A and B in a single line.

Since these numbers may be too large, print them modulo 106 + 3. Note that A and B must be coprime before their remainders modulo 106 + 3 are taken.

## Examples
```input
3 2
```
```output
1 8
```
-----
```input
1 3
```
```output
1 1
```
-----
```input
4 3
```
```output
23 128
```

## Note
In the first sample case, there are 23 = 8 days in Udayland. The probability that 2 people have the same birthday among 2 people is clearly $${ \frac { 1 } { 8 } }$$, so A = 1, B = 8.

In the second sample case, there are only 21 = 2 days in Udayland, but there are 3 people, so it is guaranteed that two of them have the same birthday. Thus, the probability is 1 and A = B = 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
Little girl Masha likes winter sports, today she's planning to take part in slalom skiing.

The track is represented as a grid composed of n × m squares. There are rectangular obstacles at the track, composed of grid squares. Masha must get from the square (1, 1) to the square (n, m). She can move from a square to adjacent square: either to the right, or upwards. If the square is occupied by an obstacle, it is not allowed to move to that square.

One can see that each obstacle can actually be passed in two ways: either it is to the right of Masha's path, or to the left. Masha likes to try all ways to do things, so she would like to know how many ways are there to pass the track. Two ways are considered different if there is an obstacle such that it is to the right of the path in one way, and to the left of the path in the other way.

Help Masha to find the number of ways to pass the track. The number of ways can be quite big, so Masha would like to know it modulo 109 + 7.

The pictures below show different ways to pass the track in sample tests.

## Input Format
The first line of input data contains three positive integers: n, m and k (3 ≤ n, m ≤ 106, 0 ≤ k ≤ 105) — the size of the track and the number of obstacles.

The following k lines contain four positive integers each: x1, y1, x2, y2 (1 ≤ x1 ≤ x2 ≤ n, 1 ≤ y1 ≤ y2 ≤ m) — coordinates of bottom left, and top right squares of the obstacle.

It is guaranteed that there are no obstacles at squares (1, 1) and (n, m), and no obstacles overlap (but some of them may touch).

## Output Format
Output one integer — the number of ways to pass the track modulo 109 + 7.

## Examples
```input
3 3 0
```
```output
1
```
-----
```input
4 5 1
2 2 3 4
```
```output
2
```
-----
```input
5 5 3
2 2 2 3
4 2 5 2
4 4 4 4
```
```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 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
Misha has an array of integers of length n. He wants to choose k different continuous subarrays, so that each element of the array belongs to at least one of the chosen subarrays.

Misha wants to choose the subarrays in such a way that if he calculated the sum of elements for each subarray, and then add up all these sums, the resulting value was maximum possible.

## Input Format
The first line of input contains two integers: n, k (1 ≤ n ≤ 100 000, 1 ≤ k ≤ n·(n + 1) / 2) — the number of elements in the array and the number of different subarrays that must be chosen.

The second line contains n integers ai ( - 50 000 ≤ ai ≤ 50 000) — the elements of the array.

## Output Format
Output one integer — the maximum possible value Misha can get by choosing k different subarrays.

## Examples
```input
5 4
6 -4 -10 -4 7
```
```output
11
```

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
Ostap is preparing to play chess again and this time he is about to prepare. Thus, he was closely monitoring one recent chess tournament. There were m players participating and each pair of players played exactly one game. The victory gives 2 points, draw — 1 points, lose — 0 points.

Ostap is lazy, so he never tries to remember the outcome of each game. Instead, he computes the total number of points earned by each of the players (the sum of his points in all games which he took part in), sort these value in non-ascending order and then remembers first n integers in this list.

Now the Great Strategist Ostap wonders whether he remembers everything correct. He considers that he is correct if there exists at least one tournament results table such that it will produce the given integers. That means, if we count the sum of points for each player, sort them and take first n elements, the result will coincide with what Ostap remembers. Can you check if such table exists?

## Input Format
The first line of the input contains two integers m and n (1 ≤ n ≤ m ≤ 3000) — the number of participants of the tournament and the number of top results Ostap remembers.

The second line contains n integers, provided in non-ascending order — the number of points earned by top participants as Ostap remembers them. It's guaranteed that this integers are non-negative and do not exceed 2·m.

## Output Format
If there is no tournament such that Ostap can obtain the given set of integers using the procedure described in the statement, then print "no" in the only line of the output. Otherwise, the first line of the output should contain the word "yes". Next m lines should provide the description of any valid tournament. Each of these lines must contain m characters 'X', 'W', 'D' and 'L'. Character 'X' should always be located on the main diagonal (and only there), that is on the i-th position of the i-th string. Character 'W' on the j-th position of the i-th string means that the i-th player won the game against the j-th. In the same way character 'L' means loose and 'D' means draw.

The table you print must be consistent and the points earned by best n participants should match the memory of Ostap. If there are many possible answers, print any of them.

## Examples
```input
5 5
8 6 4 2 0
```
```output
yes
XWWWW
LXWWW
LLXWW
LLLXW
LLLLX
```
-----
```input
5 1
9
```
```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
There exists an island called Arpa’s land, some beautiful girls live there, as ugly ones do.

Mehrdad wants to become minister of Arpa’s land. Arpa has prepared an exam. Exam has only one question, given n, print the last digit of 1378n.

Mehrdad has become quite confused and wants you to help him. Please help, although it's a naive cheat.

## Input Format
The single line of input contains one integer n (0  ≤  n  ≤  109).

## Output Format
Print single integer — the last digit of 1378n.

## Examples
```input
1
```
```output
8
```
-----
```input
2
```
```output
4
```

## Note
In the first example, last digit of 13781 = 1378 is 8.

In the second example, last digit of 13782 = 1378·1378 = 1898884 is 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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
There are some beautiful girls in Arpa’s land as mentioned before.

Once Arpa came up with an obvious problem:

Given an array and a number x, count the number of pairs of indices i, j (1 ≤ i < j ≤ n) such that $$a_i \oplus a_j = x$$, where $$\bigcirc$$ is bitwise xor operation (see notes for explanation).

Immediately, Mehrdad discovered a terrible solution that nobody trusted. Now Arpa needs your help to implement the solution to that problem.

## Input Format
First line contains two integers n and x (1 ≤ n ≤ 105, 0 ≤ x ≤ 105) — the number of elements in the array and the integer x.

Second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 105) — the elements of the array.

## Output Format
Print a single integer: the answer to the problem.

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

## Note
In the first sample there is only one pair of i = 1 and j = 2. $$a_{1} \oplus a_{2} = 3 = x$$ so the answer is 1.

In the second sample the only two pairs are i = 3, j = 4 (since $$2 \oplus 3 = 1$$) and i = 1, j = 5 (since $$5 \oplus 4 = 1$$).

A bitwise xor takes two bit integers of equal length and performs the logical xor operation on each pair of corresponding bits. The result in each position is 1 if only the first bit is 1 or only the second bit is 1, but will be 0 if both are 0 or both are 1. You can read more about bitwise xor operation here: https://en.wikipedia.org/wiki/Bitwise_operation#XOR.

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
Ilya is an experienced player in tic-tac-toe on the 4 × 4 field. He always starts and plays with Xs. He played a lot of games today with his friend Arseny. The friends became tired and didn't finish the last game. It was Ilya's turn in the game when they left it. Determine whether Ilya could have won the game by making single turn or not.

The rules of tic-tac-toe on the 4 × 4 field are as follows. Before the first turn all the field cells are empty. The two players take turns placing their signs into empty cells (the first player places Xs, the second player places Os). The player who places Xs goes first, the another one goes second. The winner is the player who first gets three of his signs in a row next to each other (horizontal, vertical or diagonal).

## Input Format
The tic-tac-toe position is given in four lines.

Each of these lines contains four characters. Each character is '.' (empty cell), 'x' (lowercase English letter x), or 'o' (lowercase English letter o). It is guaranteed that the position is reachable playing tic-tac-toe, and it is Ilya's turn now (in particular, it means that the game is not finished). It is possible that all the cells are empty, it means that the friends left without making single turn.

## Output Format
Print single line: "YES" in case Ilya could have won by making single turn, and "NO" otherwise.

## Examples
```input
xx..
.oo.
x...
oox.
```
```output
YES
```
-----
```input
x.ox
ox..
x.o.
oo.x
```
```output
NO
```
-----
```input
x..x
..oo
o...
x.xo
```
```output
YES
```
-----
```input
o.x.
o...
.x..
ooxx
```
```output
NO
```

## Note
In the first example Ilya had two winning moves: to the empty cell in the left column and to the leftmost empty cell in the first row.

In the second example it wasn't possible to win by making single turn.

In the third example Ilya could have won by placing X in the last row between two existing Xs.

In the fourth example it wasn't possible to win by making single turn.

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
All our characters have hobbies. The same is true for Fedor. He enjoys shopping in the neighboring supermarket.

The goods in the supermarket have unique integer ids. Also, for every integer there is a product with id equal to this integer. Fedor has n discount coupons, the i-th of them can be used with products with ids ranging from li to ri, inclusive. Today Fedor wants to take exactly k coupons with him.

Fedor wants to choose the k coupons in such a way that the number of such products x that all coupons can be used with this product x is as large as possible (for better understanding, see examples). Fedor wants to save his time as well, so he asks you to choose coupons for him. Help Fedor!

## Input Format
The first line contains two integers n and k (1 ≤ k ≤ n ≤ 3·105) — the number of coupons Fedor has, and the number of coupons he wants to choose.

Each of the next n lines contains two integers li and ri ( - 109 ≤ li ≤ ri ≤ 109) — the description of the i-th coupon. The coupons can be equal.

## Output Format
In the first line print single integer — the maximum number of products with which all the chosen coupons can be used. The products with which at least one coupon cannot be used shouldn't be counted.

In the second line print k distinct integers p1, p2, ..., pk (1 ≤ pi ≤ n) — the ids of the coupons which Fedor should choose.

If there are multiple answers, print any of them.

## Examples
```input
4 2
1 100
40 70
120 130
125 180
```
```output
31
1 2
```
-----
```input
3 2
1 12
15 20
25 30
```
```output
0
1 2
```
-----
```input
5 2
1 10
5 15
14 50
30 70
99 100
```
```output
21
3 4
```

## Note
In the first example if we take the first two coupons then all the products with ids in range [40, 70] can be bought with both coupons. There are 31 products in total.

In the second example, no product can be bought with two coupons, that is why the answer is 0. Fedor can choose any two coupons in this example.

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: 512.0 MB

# Problem
There are literally dozens of snooker competitions held each year, and team Jinotega tries to attend them all (for some reason they prefer name "snookah")! When a competition takes place somewhere far from their hometown, Ivan, Artsem and Konstantin take a flight to the contest and back.

Jinotega's best friends, team Base have found a list of their itinerary receipts with information about departure and arrival airports. Now they wonder, where is Jinotega now: at home or at some competition far away? They know that:

- this list contains all Jinotega's flights in this year (in arbitrary order),
- Jinotega has only flown from his hometown to a snooker contest and back,
- after each competition Jinotega flies back home (though they may attend a competition in one place several times),
- and finally, at the beginning of the year Jinotega was at home.

Please help them to determine Jinotega's location!

## Input Format
In the first line of input there is a single integer n: the number of Jinotega's flights (1 ≤ n ≤ 100). In the second line there is a string of 3 capital Latin letters: the name of Jinotega's home airport. In the next n lines there is flight information, one flight per line, in form "XXX->YYY", where "XXX" is the name of departure airport "YYY" is the name of arrival airport. Exactly one of these airports is Jinotega's home airport.

It is guaranteed that flights information is consistent with the knowledge of Jinotega's friends, which is described in the main part of the statement.

## Output Format
If Jinotega is now at home, print "home" (without quotes), otherwise print "contest".

## Examples
```input
4
SVO
SVO->CDG
LHR->SVO
SVO->LHR
CDG->SVO
```
```output
home
```
-----
```input
3
SVO
SVO->HKT
HKT->SVO
SVO->RAP
```
```output
contest
```

## Note
In the first sample Jinotega might first fly from SVO to CDG and back, and then from SVO to LHR and back, so now they should be at home. In the second sample Jinotega must now be at RAP because a flight from RAP back to SVO is not on the list.

Now solve the problem and return the code.