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
Yaroslav is playing a computer game, and at one of the levels, he encountered $$$n$$$ mushrooms arranged in a row. Each mushroom has its own level of toxicity; the $$$i$$$-th mushroom from the beginning has a toxicity level of $$$a_i$$$. Yaroslav can choose two integers $$$1 \le l \le r \le n$$$, and then his character will take turns from left to right to eat mushrooms from this subsegment one by one, i.e., the mushrooms with numbers $$$l, l+1, l+2, \ldots, r$$$.

The character has a toxicity level $$$g$$$, initially equal to $$$0$$$. The computer game is defined by the number $$$x$$$ — the maximum toxicity level at any given time. When eating a mushroom with toxicity level $$$k$$$, the following happens:

1. The toxicity level of the character is increased by $$$k$$$.
2. If $$$g \leq x$$$, the process continues; otherwise, $$$g$$$ becomes zero and the process continues.

Yaroslav became interested in how many ways there are to choose the values of $$$l$$$ and $$$r$$$ such that the final value of $$$g$$$ is not zero. Help Yaroslav find this number!

## Input Format
Each test consists of multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^{4}$$$) — the number of test cases. Then follows the description of the test cases.

The first line of each test case contains two integers $$$n$$$, $$$x$$$ ($$$1 \leq n \leq 2 \cdot 10^5, 1 \le x \le 10^9$$$) — the number of mushrooms and the maximum toxicity level.

The second line of each test case contains $$$n$$$ numbers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

## Output Format
For each test case, output a single number — the number of subsegments such that the final value of $$$g$$$ will not be zero.

## Examples
```input
5
4 2
1 1 1 1
3 2
1 2 3
1 6
10
6 3
1 2 1 4 3 8
5 999999999
999999999 999999998 1000000000 1000000000 500000000
```
```output
8
2
0
10
7
```

## Note
In the first test case, the subsegments $$$(1, 1)$$$, $$$(1, 2)$$$, $$$(1, 4)$$$, $$$(2, 2)$$$, $$$(2, 3)$$$, $$$(3, 3)$$$, $$$(3, 4)$$$ and $$$(4, 4)$$$ are suitable.

In the second test case, non-zero $$$g$$$ will remain only on the subsegments $$$(1, 1)$$$ and $$$(2, 2)$$$.

In the third test case, on the only possible subsegment, $$$g$$$ will be zero.

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
Vanya has a graph with $$$n$$$ vertices (numbered from $$$1$$$ to $$$n$$$) and an array $$$a$$$ of $$$n$$$ integers; initially, there are no edges in the graph. Vanya got bored, and to have fun, he decided to perform $$$n - 1$$$ operations.

Operation number $$$x$$$ (operations are numbered in order starting from $$$1$$$) is as follows:

- Choose $$$2$$$ different numbers $$$1 \leq u,v \leq n$$$, such that $$$|a_u - a_v|$$$ is divisible by $$$x$$$.
- Add an undirected edge between vertices $$$u$$$ and $$$v$$$ to the graph.

Help Vanya get a connected$$$^{\text{∗}}$$$ graph using the $$$n - 1$$$ operations, or determine that it is impossible.

## Input Format
Each test consists of multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^{3}$$$) — the number of test cases. Then follows the description of the test cases.

The first line of each test case contains the number $$$n$$$ ($$$1 \leq n \leq 2000$$$) — the number of vertices in the graph.

The second line of each test case contains $$$n$$$ numbers $$$a_1, a_2, \cdots a_n$$$ ($$$1 \leq a_i \leq 10^9$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2000$$$.

## Output Format
For each test case, if there is no solution, then output "No" (without quotes).

Otherwise, output "Yes" (without quotes), and then output $$$n - 1$$$ lines, where in the $$$i$$$-th line, output the numbers $$$u$$$ and $$$v$$$ that need to be chosen for operation $$$i$$$.

You can output each letter in any case (for example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as a positive answer).

## Examples
```input
8
2
1 4
4
99 7 1 13
5
10 2 31 44 73
5
87 6 81 44 32
5
62 35 33 79 16
5
6 51 31 69 42
5
52 63 25 21 5
12
33 40 3 11 31 43 37 8 50 5 12 22
```
```output
YES
2 1
YES
4 1
2 1
3 2
YES
5 1
4 1
3 1
2 1
YES
4 1
3 1
2 1
5 4
YES
3 1
5 1
2 1
4 2
YES
4 1
5 1
2 1
3 2
YES
2 1
5 2
3 1
4 3
YES
9 1
12 9
11 1
10 1
6 1
7 6
2 1
8 2
5 2
3 1
4 1
```

## Note
Let's consider the second test case.

- First operation $$$(x = 1)$$$: we can connect vertices $$$4$$$ and $$$1$$$, since $$$|a_4 - a_1| = |13 - 99| = |-86| = 86$$$, and $$$86$$$ is divisible by $$$1$$$.

- Second operation $$$(x = 2)$$$: we can connect vertices $$$2$$$ and $$$1$$$, since $$$|a_2 - a_1| = |7 - 99| = |-92| = 92$$$, and $$$92$$$ is divisible by $$$2$$$.

- Third operation $$$(x = 3)$$$: we can connect vertices $$$3$$$ and $$$2$$$, since $$$|a_3 - a_2| = |1 - 7| = |-6| = 6$$$, and $$$6$$$ is divisible by $$$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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Pelican Town represents $$$n$$$ houses connected by $$$m$$$ bidirectional roads. Some roads have NPCs standing on them. Farmer Buba needs to walk on each road with an NPC and talk to them.

Help the farmer find a route satisfying the following properties:

- The route starts at some house, follows the roads, and ends at the same house.
- The route does not follow any road more than once (in both directions together).
- The route follows each road with an NPC exactly once.

It is guaranteed that you can reach any house from any other by walking on the roads with NPCs only.

## Input Format
Each test consists of multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^{4}$$$) — the number of test cases. Then follows the description of the test cases.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$2 \leq n \leq 5 \cdot 10^5, 1 \leq m \leq 5 \cdot 10^5$$$) — the number of houses and roads in Pelican Town respectively.

In each of the next $$$m$$$ lines, three integers $$$u$$$, $$$v$$$, and $$$c$$$ ($$$1 \leq u, v \leq n, c = 0/1$$$) are given — the ends of the road and whether an NPC is on this road. If $$$c = 1$$$, then the road has an NPC. If $$$c = 0$$$, then the road has no NPC.

The graph may contain multiple edges and loops, and if there are multiple edges with NPCs standing on them, the route must follow each of these roads.

It is guaranteed that you can reach any house from any other by walking on the roads with NPCs only.

It is guaranteed that the sum of $$$n$$$ and $$$m$$$ for all test cases does not exceed $$$5 \cdot 10^5$$$.

## Output Format
For each test case, if there is no solution, then output "No" (without quotes).

Otherwise, output "Yes" (without quotes), and then output $$$k$$$ — the number of roads in the route. In the next line, output $$$k + 1$$$ numbers — the houses of the route in the order of traversal. Note that the first house should match the last one, as the route is cyclic.

If there are multiple answers, you can print any of them.

You can output each letter in any case (for example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as a positive answer).

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

## Note
Note that in the third test case, there are multiple edges $$$(5, 2)$$$. You must walk on two of them.

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

# Problem
After winning another Bed Wars game, Masha and Olya wanted to relax and decided to play a new game. Masha gives Olya an array $$$a$$$ of length $$$n$$$ and a number $$$s$$$. Now Olya's task is to find a non-negative number $$$x$$$ such that $$$\displaystyle\sum_{i=1}^{n} a_i \oplus x = s$$$. But she is very tired after a tight round, so please help her with this.

But this task seemed too simple to them, so they decided to make the numbers larger (up to $$$2^k$$$) and provide you with their binary representation.

## Input Format
Each test consists of several test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. Then follows the description of the test cases.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n, k, n \cdot k \le 2 \cdot 10^6$$$) — the length of the array $$$a$$$ and the length of the binary representation of all numbers.

The second line contains a string of length $$$k$$$, consisting of zeros and ones — the binary representation of the number $$$s$$$, starting from the most significant bits.

The next $$$n$$$ lines also contain strings of length $$$k$$$, consisting of zeros and ones, the $$$i$$$-th of these strings contains the binary representation of the number $$$a_i$$$, starting from the most significant bits.

It is guaranteed that the sum of the values $$$n \cdot k$$$ for all test cases does not exceed $$$2 \cdot 10^6$$$.

## Output Format
For each test case, output a string of length $$$k$$$ on a separate line, consisting of zeros or ones — the binary representation of any suitable number $$$x$$$ ($$$x \ge 0$$$), starting from the most significant bits, or $$$-1$$$ if such $$$x$$$ does not exist.

## Examples
```input
4
4 5
01011
01110
00110
01100
01111
2 8
00101001
10111111
10011110
5 4
0101
0010
0000
0000
0010
0011
6 5
00011
10110
11001
01010
11100
10011
10000
```
```output
01110
10011010
0010
-1
```

## Note
In the first test case, $$$s = 11, a = [14, 6, 12, 15]$$$, if $$$x = 14$$$, then $$$\displaystyle\sum_{i=1}^{n} a_i \oplus x = (14 \oplus 14) + (6 \oplus 14) + (12 \oplus 14) + (15 \oplus 14) = 0 + 8 + 2 + 1 = 11 = s$$$.

In the second test case, $$$s = 41, a = [191, 158]$$$, if $$$x = 154$$$, then $$$\displaystyle\sum_{i=1}^{n} a_i \oplus x = (191 \oplus 154) + (158 \oplus 154) = 37 + 4 = 41 = s$$$.

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
Once Bob needed to find the second order statistics of a sequence of integer numbers. Lets choose each number from the sequence exactly once and sort them. The value on the second position is the second order statistics of the given sequence. In other words it is the smallest element strictly greater than the minimum. Help Bob solve this problem.

## Input Format
The first input line contains integer n (1 ≤ n ≤ 100) — amount of numbers in the sequence. The second line contains n space-separated integer numbers — elements of the sequence. These numbers don't exceed 100 in absolute value.

## Output Format
If the given sequence has the second order statistics, output this order statistics, otherwise output NO.

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

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
Bob wants to put a new bargaining table in his office. To do so he measured the office room thoroughly and drew its plan: Bob's office room is a rectangular room n × m meters. Each square meter of the room is either occupied by some furniture, or free. A bargaining table is rectangular, and should be placed so, that its sides are parallel to the office walls. Bob doesn't want to change or rearrange anything, that's why all the squares that will be occupied by the table should be initially free. Bob wants the new table to sit as many people as possible, thus its perimeter should be maximal. Help Bob find out the maximum possible perimeter of a bargaining table for his office.

## Input Format
The first line contains 2 space-separated numbers n and m (1 ≤ n, m ≤ 25) — the office room dimensions. Then there follow n lines with m characters 0 or 1 each. 0 stands for a free square meter of the office room. 1 stands for an occupied square meter. It's guaranteed that at least one square meter in the room is free.

## Output Format
Output one number — the maximum possible perimeter of a bargaining table for Bob's office room.

## Examples
```input
3 3
000
010
000
```
```output
8
```
-----
```input
5 4
1100
0000
0000
0000
0000
```
```output
16
```

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
Bob got a job as a system administrator in X corporation. His first task was to connect n servers with the help of m two-way direct connection so that it becomes possible to transmit data from one server to any other server via these connections. Each direct connection has to link two different servers, each pair of servers should have at most one direct connection. Y corporation, a business rival of X corporation, made Bob an offer that he couldn't refuse: Bob was asked to connect the servers in such a way, that when server with index v fails, the transmission of data between some other two servers becomes impossible, i.e. the system stops being connected. Help Bob connect the servers.

## Input Format
The first input line contains 3 space-separated integer numbers n, m, v (3 ≤ n ≤ 105, 0 ≤ m ≤ 105, 1 ≤ v ≤ n), n — amount of servers, m — amount of direct connections, v — index of the server that fails and leads to the failure of the whole system.

## Output Format
If it is impossible to connect the servers in the required way, output -1. Otherwise output m lines with 2 numbers each — description of all the direct connections in the system. Each direct connection is described by two numbers — indexes of two servers, linked by this direct connection. The servers are numbered from 1. If the answer is not unique, output any.

## Examples
```input
5 6 3
```
```output
1 2
2 3
3 4
4 5
1 3
3 5
```
-----
```input
6 100 1
```
```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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You are given n segments on the Ox-axis. You can drive a nail in any integer point on the Ox-axis line nail so, that all segments containing this point, are considered nailed down. If the nail passes through endpoint of some segment, this segment is considered to be nailed too. What is the smallest number of nails needed to nail all the segments down?

## Input Format
The first line of the input contains single integer number n (1 ≤ n ≤ 1000) — amount of segments. Following n lines contain descriptions of the segments. Each description is a pair of integer numbers — endpoints coordinates. All the coordinates don't exceed 10000 by absolute value. Segments can degenarate to points.

## Output Format
The first line should contain one integer number — the smallest number of nails needed to nail all the segments down. The second line should contain coordinates of driven nails separated by space in any order. If the answer is not unique, output any.

## Examples
```input
2
0 2
2 5
```
```output
1
2
```
-----
```input
5
0 3
4 2
4 8
8 10
7 7
```
```output
3
7 10 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: 6.0 seconds
Memory limit: 256.0 MB

# Problem
You have n friends and you want to take m pictures of them. Exactly two of your friends should appear in each picture and no two pictures should contain the same pair of your friends. So if you have n = 3 friends you can take 3 different pictures, each containing a pair of your friends.

Each of your friends has an attractiveness level which is specified by the integer number ai for the i-th friend. You know that the attractiveness of a picture containing the i-th and the j-th friends is equal to the exclusive-or (xor operation) of integers ai and aj.

You want to take pictures in a way that the total sum of attractiveness of your pictures is maximized. You have to calculate this value. Since the result may not fit in a 32-bit integer number, print it modulo 1000000007 (109 + 7).

## Input Format
The first line of input contains two integers n and m $$( 1 \leq n \leq 5 \cdot 1 0 ^ { 4 } ; \; 0 \leq m \leq \frac { n \cdot ( n - 1 ) } { 2 } )$$ — the number of friends and the number of pictures that you want to take.

Next line contains n space-separated integers a1, a2, ..., an (0 ≤ ai ≤ 109) — the values of attractiveness of the friends.

## Output Format
The only line of output should contain an integer — the optimal total sum of attractiveness of your pictures.

## Examples
```input
3 1
1 2 3
```
```output
3
```
-----
```input
3 2
1 2 3
```
```output
5
```
-----
```input
3 3
1 2 3
```
```output
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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Vasya is an active Internet user. One day he came across an Internet resource he liked, so he wrote its address in the notebook. We know that the address of the written resource has format:

<protocol>://<domain>.ru[/<context>]

where:

- <protocol> can equal either "http" (without the quotes) or "ftp" (without the quotes),
- <domain> is a non-empty string, consisting of lowercase English letters,
- the /<context> part may not be present. If it is present, then <context> is a non-empty string, consisting of lowercase English letters.

If string <context> isn't present in the address, then the additional character "/" isn't written. Thus, the address has either two characters "/" (the ones that go before the domain), or three (an extra one in front of the context).

When the boy came home, he found out that the address he wrote in his notebook had no punctuation marks. Vasya must have been in a lot of hurry and didn't write characters ":", "/", ".".

Help Vasya to restore the possible address of the recorded Internet resource.

## Input Format
The first line contains a non-empty string that Vasya wrote out in his notebook. This line consists of lowercase English letters only.

It is guaranteed that the given string contains at most 50 letters. It is guaranteed that the given string can be obtained from some correct Internet resource address, described above.

## Output Format
Print a single line — the address of the Internet resource that Vasya liked. If there are several addresses that meet the problem limitations, you are allowed to print any of them.

## Examples
```input
httpsunrux
```
```output
http://sun.ru/x
```
-----
```input
ftphttprururu
```
```output
ftp://http.ru/ruru
```

## Note
In the second sample there are two more possible answers: "ftp://httpruru.ru" and "ftp://httpru.ru/ru".

Now solve the problem and return the code.