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: 2.0 seconds
Memory limit: 512.0 MB

# Problem
Leo Jr. draws pictures in his notebook with checkered sheets (that is, each sheet has a regular square grid printed on it). We can assume that the sheets are infinitely large in any direction.

To draw a picture, Leo Jr. colors some of the cells on a sheet gray. He considers the resulting picture beautiful if the following conditions are satisfied:

- The picture is connected, that is, it is possible to get from any gray cell to any other by following a chain of gray cells, with each pair of adjacent cells in the path being neighbours (that is, sharing a side).
- Each gray cell has an even number of gray neighbours.
- There are exactly $$$n$$$ gray cells with all gray neighbours. The number of other gray cells can be arbitrary (but reasonable, so that they can all be listed).

Leo Jr. is now struggling to draw a beautiful picture with a particular choice of $$$n$$$. Help him, and provide any example of a beautiful picture.

To output cell coordinates in your answer, assume that the sheet is provided with a Cartesian coordinate system such that one of the cells is chosen to be the origin $$$(0, 0)$$$, axes $$$0x$$$ and $$$0y$$$ are orthogonal and parallel to grid lines, and a unit step along any axis in any direction takes you to a neighbouring cell.

## Input Format
The only line contains a single integer $$$n$$$ ($$$1 \leq n \leq 500$$$) — the number of gray cells with all gray neighbours in a beautiful picture.

## Output Format
In the first line, print a single integer $$$k$$$ — the number of gray cells in your picture. For technical reasons, $$$k$$$ should not exceed $$$5 \cdot 10^5$$$.

Each of the following $$$k$$$ lines should contain two integers — coordinates of a gray cell in your picture. All listed cells should be distinct, and the picture should satisdfy all the properties listed above. All coordinates should not exceed $$$10^9$$$ by absolute value.

One can show that there exists an answer satisfying all requirements with a small enough $$$k$$$.

## Examples
```input
4
```
```output
12
1 0
2 0
0 1
1 1
2 1
3 1
0 2
1 2
2 2
3 2
1 3
2 3
```

## Note
The answer for the sample is pictured below:

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
Gottfried learned about binary number representation. He then came up with this task and presented it to you.

You are given a collection of $$$n$$$ non-negative integers $$$a_1, \ldots, a_n$$$. You are allowed to perform the following operation: choose two distinct indices $$$1 \leq i, j \leq n$$$. If before the operation $$$a_i = x$$$, $$$a_j = y$$$, then after the operation $$$a_i = x~\mathsf{AND}~y$$$, $$$a_j = x~\mathsf{OR}~y$$$, where $$$\mathsf{AND}$$$ and $$$\mathsf{OR}$$$ are bitwise AND and OR respectively (refer to the Notes section for formal description). The operation may be performed any number of times (possibly zero).

After all operations are done, compute $$$\sum_{i=1}^n a_i^2$$$ — the sum of squares of all $$$a_i$$$. What is the largest sum of squares you can achieve?

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

The second line contains $$$n$$$ integers $$$a_1, \ldots, a_n$$$ ($$$0 \leq a_i < 2^{20}$$$).

## Output Format
Print a single integer — the largest possible sum of squares that can be achieved after several (possibly zero) operations.

## Examples
```input
1
123
```
```output
15129
```
-----
```input
3
1 3 5
```
```output
51
```
-----
```input
2
349525 699050
```
```output
1099509530625
```

## Note
In the first sample no operation can be made, thus the answer is $$$123^2$$$.

In the second sample we can obtain the collection $$$1, 1, 7$$$, and $$$1^2 + 1^2 + 7^2 = 51$$$.

If $$$x$$$ and $$$y$$$ are represented in binary with equal number of bits (possibly with leading zeros), then each bit of $$$x~\mathsf{AND}~y$$$ is set to $$$1$$$ if and only if both corresponding bits of $$$x$$$ and $$$y$$$ are set to $$$1$$$. Similarly, each bit of $$$x~\mathsf{OR}~y$$$ is set to $$$1$$$ if and only if at least one of the corresponding bits of $$$x$$$ and $$$y$$$ are set to $$$1$$$. For example, $$$x = 3$$$ and $$$y = 5$$$ are represented as $$$011_2$$$ and $$$101_2$$$ (highest bit first). Then, $$$x~\mathsf{AND}~y = 001_2 = 1$$$, and $$$x~\mathsf{OR}~y = 111_2 = 7$$$.

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
This is an easier version of the problem H without modification queries.

Lester and Delbert work at an electronics company. They are currently working on a microchip component serving to connect two independent parts of a large supercomputer.

The component is built on top of a breadboard — a grid-like base for a microchip. The breadboard has $$$n$$$ rows and $$$m$$$ columns, and each row-column intersection contains a node. Also, on each side of the breadboard there are ports that can be attached to adjacent nodes. Left and right side have $$$n$$$ ports each, and top and bottom side have $$$m$$$ ports each. Each of the ports is connected on the outside to one of the parts bridged by the breadboard, and is colored red or blue respectively.

Ports can be connected by wires going inside the breadboard. However, there are a few rules to follow:

- Each wire should connect a red port with a blue port, and each port should be connected to at most one wire.
- Each part of the wire should be horizontal or vertical, and turns are only possible at one of the nodes.
- To avoid interference, wires can not have common parts of non-zero length (but may have common nodes). Also, a wire can not cover the same segment of non-zero length twice.

The capacity of the breadboard is the largest number of red-blue wire connections that can be made subject to the rules above. For example, the breadboard above has capacity $$$7$$$, and one way to make seven connections is pictured below.

Up to this point statements of both versions are identical. Differences follow below.

Given the current breadboard configuration, help Lester and Delbert find its capacity efficiently.

## Input Format
The first line contains three integers $$$n, m, q$$$ ($$$1 \leq n, m \leq 10^5$$$, $$$\pmb{q = 0}$$$). $$$n$$$ and $$$m$$$ are the number of rows and columns of the breadboard respectively. In this version $$$q$$$ is always zero, and is only present for consistency with the harder version.

The next four lines describe initial coloring of the ports. Each character in these lines is either R or B, depending on the coloring of the respective port. The first two of these lines contain $$$n$$$ characters each, and describe ports on the left and right sides respectively from top to bottom. The last two lines contain $$$m$$$ characters each, and describe ports on the top and bottom sides respectively from left to right.

## Output Format
Print a single integer — the given breadboard capacity.

## Examples
```input
4 5 0
BBRR
RBBR
BBBBB
RRRRR
```
```output
7
```

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
Let $$$LCM(x, y)$$$ be the minimum positive integer that is divisible by both $$$x$$$ and $$$y$$$. For example, $$$LCM(13, 37) = 481$$$, $$$LCM(9, 6) = 18$$$.

You are given two integers $$$l$$$ and $$$r$$$. Find two integers $$$x$$$ and $$$y$$$ such that $$$l \le x < y \le r$$$ and $$$l \le LCM(x, y) \le r$$$.

## Input Format
The first line contains one integer $$$t$$$ ($$$1 \le t \le 10000$$$) — the number of test cases.

Each test case is represented by one line containing two integers $$$l$$$ and $$$r$$$ ($$$1 \le l < r \le 10^9$$$).

## Output Format
For each test case, print two integers:

- if it is impossible to find integers $$$x$$$ and $$$y$$$ meeting the constraints in the statement, print two integers equal to $$$-1$$$;
- otherwise, print the values of $$$x$$$ and $$$y$$$ (if there are multiple valid answers, you may print any of them).

## Examples
```input
4
1 1337
13 69
2 4
88 89
```
```output
6 7
14 21
2 4
-1 -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: 2.0 seconds
Memory limit: 256.0 MB

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

Initially you are standing at index $$$1$$$ and have a score equal to $$$a_1$$$. You can perform two kinds of moves:

1. move right — go from your current index $$$x$$$ to $$$x+1$$$ and add $$$a_{x+1}$$$ to your score. This move can only be performed if $$$x<n$$$.
2. move left — go from your current index $$$x$$$ to $$$x-1$$$ and add $$$a_{x-1}$$$ to your score. This move can only be performed if $$$x>1$$$. Also, you can't perform two or more moves to the left in a row.

You want to perform exactly $$$k$$$ moves. Also, there should be no more than $$$z$$$ moves to the left among them.

What is the maximum score you can achieve?

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of testcases.

The first line of each testcase contains three integers $$$n, k$$$ and $$$z$$$ ($$$2 \le n \le 10^5$$$, $$$1 \le k \le n - 1$$$, $$$0 \le z \le min(5, k)$$$) — the number of elements in the array, the total number of moves you should perform and the maximum number of moves to the left you can perform.

The second line of each testcase contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^4$$$) — the given array.

The sum of $$$n$$$ over all testcases does not exceed $$$3 \cdot 10^5$$$.

## Output Format
Print $$$t$$$ integers — for each testcase output the maximum score you can achieve if you make exactly $$$k$$$ moves in total, no more than $$$z$$$ of them are to the left and there are no two or more moves to the left in a row.

## Examples
```input
4
5 4 0
1 5 4 3 2
5 4 1
1 5 4 3 2
5 4 4
10 20 30 40 50
10 7 3
4 6 8 2 9 9 7 4 10 9
```
```output
15
19
150
56
```

## Note
In the first testcase you are not allowed to move left at all. So you make four moves to the right and obtain the score $$$a_1 + a_2 + a_3 + a_4 + a_5$$$.

In the second example you can move one time to the left. So we can follow these moves: right, right, left, right. The score will be $$$a_1 + a_2 + a_3 + a_2 + a_3$$$.

In the third example you can move four times to the left but it's not optimal anyway, you can just move four times to the right and obtain the score $$$a_1 + a_2 + a_3 + a_4 + a_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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Let's call left cyclic shift of some string $$$t_1 t_2 t_3 \dots t_{n - 1} t_n$$$ as string $$$t_2 t_3 \dots t_{n - 1} t_n t_1$$$.

Analogically, let's call right cyclic shift of string $$$t$$$ as string $$$t_n t_1 t_2 t_3 \dots t_{n - 1}$$$.

Let's say string $$$t$$$ is good if its left cyclic shift is equal to its right cyclic shift.

You are given string $$$s$$$ which consists of digits 0–9.

What is the minimum number of characters you need to erase from $$$s$$$ to make it good?

## Input Format
The first line contains single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.

Next $$$t$$$ lines contains test cases — one per line. The first and only line of each test case contains string $$$s$$$ ($$$2 \le |s| \le 2 \cdot 10^5$$$). Each character $$$s_i$$$ is digit 0–9.

It's guaranteed that the total length of strings doesn't exceed $$$2 \cdot 10^5$$$.

## Output Format
For each test case, print the minimum number of characters you need to erase from $$$s$$$ to make it good.

## Examples
```input
3
95831
100120013
252525252525
```
```output
3
5
0
```

## Note
In the first test case, you can erase any $$$3$$$ characters, for example, the $$$1$$$-st, the $$$3$$$-rd, and the $$$4$$$-th. You'll get string 51 and it is good.

In the second test case, we can erase all characters except 0: the remaining string is 0000 and it's good.

In the third test case, the given string $$$s$$$ is already good.

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
Berland year consists of $$$m$$$ months with $$$d$$$ days each. Months are numbered from $$$1$$$ to $$$m$$$. Berland week consists of $$$w$$$ days. The first day of the year is also the first day of the week. Note that the last week of the year might be shorter than $$$w$$$ days.

A pair $$$(x, y)$$$ such that $$$x < y$$$ is ambiguous if day $$$x$$$ of month $$$y$$$ is the same day of the week as day $$$y$$$ of month $$$x$$$.

Count the number of ambiguous pairs.

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of testcases.

Each of the next $$$t$$$ lines contains three integers $$$m$$$, $$$d$$$ and $$$w$$$ ($$$1 \le m, d, w \le 10^9$$$) — the number of months in a year, the number of days in a month and the number of days in a week.

## Output Format
Print $$$t$$$ integers — for each testcase output the number of pairs $$$(x, y)$$$ such that $$$x < y$$$ and day $$$x$$$ of month $$$y$$$ is the same day of the week as day $$$y$$$ of month $$$x$$$.

## Examples
```input
5
6 7 4
10 7 12
12 30 7
1 1 1
3247834 10298779 625324
```
```output
6
9
5
0
116461800
```

## Note
Here are the pairs for the first test case:

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 $$$n$$$ segments $$$[l_1, r_1], [l_2, r_2], \dots, [l_n, r_n]$$$. Each segment has one of two colors: the $$$i$$$-th segment's color is $$$t_i$$$.

Let's call a pair of segments $$$i$$$ and $$$j$$$ bad if the following two conditions are met:

- $$$t_i \ne t_j$$$;
- the segments $$$[l_i, r_i]$$$ and $$$[l_j, r_j]$$$ intersect, embed or touch, i. e. there exists an integer $$$x$$$ such that $$$x \in [l_i, r_i]$$$ and $$$x \in [l_j, r_j]$$$.

Calculate the maximum number of segments that can be selected from the given ones, so that there is no bad pair among the selected ones.

## Input Format
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — number of segments.

The next $$$n$$$ lines contains three integers $$$l_i, r_i, t_i$$$ ($$$1 \le l_i \le r_i \le 10^9; t_i \in \{1, 2\}$$$) — description of the $$$i$$$-th segment.

## Output Format
Print the maximum number of segments that can be selected, so that there is no bad pair among the selected segments.

## Examples
```input
3
1 3 1
4 6 2
2 5 1
```
```output
2
```
-----
```input
5
5 8 1
1 3 2
3 4 2
6 6 1
2 10 2
```
```output
4
```
-----
```input
7
19 20 1
13 15 2
6 11 2
4 10 1
14 17 1
13 13 2
5 9 1
```
```output
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
Boboniu gives you

- $$$r$$$ red balls,
- $$$g$$$ green balls,
- $$$b$$$ blue balls,
- $$$w$$$ white balls.

He allows you to do the following operation as many times as you want:

- Pick a red ball, a green ball, and a blue ball and then change their color to white.

You should answer if it's possible to arrange all the balls into a palindrome after several (possibly zero) number of described operations.

## Input Format
The first line contains one integer $$$T$$$ ($$$1\le T\le 100$$$) denoting the number of test cases.

For each of the next $$$T$$$ cases, the first line contains four integers $$$r$$$, $$$g$$$, $$$b$$$ and $$$w$$$ ($$$0\le r,g,b,w\le 10^9$$$).

## Output Format
For each test case, print "Yes" if it's possible to arrange all the balls into a palindrome after doing several (possibly zero) number of described operations. Otherwise, print "No".

## Examples
```input
4
0 1 1 1
8 1 9 3
0 0 0 0
1000000000 1000000000 1000000000 1000000000
```
```output
No
Yes
Yes
Yes
```

## Note
In the first test case, you're not able to do any operation and you can never arrange three balls of distinct colors into a palindrome.

In the second test case, after doing one operation, changing $$$(8,1,9,3)$$$ to $$$(7,0,8,6)$$$, one of those possible palindromes may be "rrrwwwbbbbrbbbbwwwrrr".

A palindrome is a word, phrase, or sequence that reads the same backwards as forwards. For example, "rggbwbggr", "b", "gg" are palindromes while "rgbb", "gbbgr" are not. Notice that an empty word, phrase, or sequence is palindrome.

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

# Problem
Boboniu likes playing chess with his employees. As we know, no employee can beat the boss in the chess game, so Boboniu has never lost in any round.

You are a new applicant for his company. Boboniu will test you with the following chess question:

Consider a $$$n\times m$$$ grid (rows are numbered from $$$1$$$ to $$$n$$$, and columns are numbered from $$$1$$$ to $$$m$$$). You have a chess piece, and it stands at some cell $$$(S_x,S_y)$$$ which is not on the border (i.e. $$$2 \le S_x \le n-1$$$ and $$$2 \le S_y \le m-1$$$).

From the cell $$$(x,y)$$$, you can move your chess piece to $$$(x,y')$$$ ($$$1\le y'\le m, y' \neq y$$$) or $$$(x',y)$$$ ($$$1\le x'\le n, x'\neq x$$$). In other words, the chess piece moves as a rook. From the cell, you can move to any cell on the same row or column.

Your goal is to visit each cell exactly once. Can you find a solution?

Note that cells on the path between two adjacent cells in your route are not counted as visited, and it is not required to return to the starting point.

## Input Format
The only line of the input contains four integers $$$n$$$, $$$m$$$, $$$S_x$$$ and $$$S_y$$$ ($$$3\le n,m\le 100$$$, $$$2 \le S_x \le n-1$$$, $$$2 \le S_y \le m-1$$$) — the number of rows, the number of columns, and the initial position of your chess piece, respectively.

## Output Format
You should print $$$n\cdot m$$$ lines.

The $$$i$$$-th line should contain two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \leq x_i \leq n$$$, $$$1 \leq y_i \leq m$$$), denoting the $$$i$$$-th cell that you visited. You should print exactly $$$nm$$$ pairs $$$(x_i, y_i)$$$, they should cover all possible pairs $$$(x_i, y_i)$$$, such that $$$1 \leq x_i \leq n$$$, $$$1 \leq y_i \leq m$$$.

We can show that under these constraints there always exists a solution. If there are multiple answers, print any.

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

## Note
Possible routes for two examples:

Now solve the problem and return the code.