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
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 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
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 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
Consider a conveyor belt represented using a grid consisting of $$$n$$$ rows and $$$m$$$ columns. The cell in the $$$i$$$-th row from the top and the $$$j$$$-th column from the left is labelled $$$(i,j)$$$.

Every cell, except $$$(n,m)$$$, has a direction R (Right) or D (Down) assigned to it. If the cell $$$(i,j)$$$ is assigned direction R, any luggage kept on that will move to the cell $$$(i,j+1)$$$. Similarly, if the cell $$$(i,j)$$$ is assigned direction D, any luggage kept on that will move to the cell $$$(i+1,j)$$$. If at any moment, the luggage moves out of the grid, it is considered to be lost.

There is a counter at the cell $$$(n,m)$$$ from where all luggage is picked. A conveyor belt is called functional if and only if any luggage reaches the counter regardless of which cell it is placed in initially. More formally, for every cell $$$(i,j)$$$, any luggage placed in this cell should eventually end up in the cell $$$(n,m)$$$.

This may not hold initially; you are, however, allowed to change the directions of some cells to make the conveyor belt functional. Please determine the minimum amount of cells you have to change.

Please note that it is always possible to make any conveyor belt functional by changing the directions of some set of cells.

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10$$$). Description of the test cases follows.

The first line of each test case contains two integers $$$n, m$$$ ($$$1 \le n \le 100$$$, $$$1 \le m \le 100$$$)  — the number of rows and columns, respectively.

The following $$$n$$$ lines each contain $$$m$$$ characters. The $$$j$$$-th character in the $$$i$$$-th line, $$$a_{i,j}$$$ is the initial direction of the cell $$$(i, j)$$$. Please note that $$$a_{n,m}=$$$ C.

## Output Format
For each case, output in a new line the minimum number of cells that you have to change to make the conveyor belt functional.

## Examples
```input
4
3 3
RRD
DDR
RRC
1 4
DDDC
6 9
RDDDDDRRR
RRDDRRDDD
RRDRDRRDR
DDDDRDDRR
DRRDRDDDR
DDRDRRDDC
1 1
C
```
```output
1
3
9
0
```

## Note
In the first case, just changing the direction of $$$(2,3)$$$ to D is enough.

You can verify that the resulting belt is functional. For example, if we place any luggage at $$$(2,2)$$$, it first moves to $$$(3,2)$$$ and then to $$$(3,3)$$$.

In the second case, we have no option but to change the first $$$3$$$ cells from D to R making the grid equal to RRRC.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array) and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).

Consider a permutation $$$p$$$ of length $$$n$$$, we build a graph of size $$$n$$$ using it as follows:

- For every $$$1 \leq i \leq n$$$, find the largest $$$j$$$ such that $$$1 \leq j < i$$$ and $$$p_j > p_i$$$, and add an undirected edge between node $$$i$$$ and node $$$j$$$
- For every $$$1 \leq i \leq n$$$, find the smallest $$$j$$$ such that $$$i < j \leq n$$$ and $$$p_j > p_i$$$, and add an undirected edge between node $$$i$$$ and node $$$j$$$

In cases where no such $$$j$$$ exists, we make no edges. Also, note that we make edges between the corresponding indices, not the values at those indices.

For clarity, consider as an example $$$n = 4$$$, and $$$p = [3,1,4,2]$$$; here, the edges of the graph are $$$(1,3),(2,1),(2,3),(4,3)$$$.

A permutation $$$p$$$ is cyclic if the graph built using $$$p$$$ has at least one simple cycle.

Given $$$n$$$, find the number of cyclic permutations of length $$$n$$$. Since the number may be very large, output it modulo $$$10^9+7$$$.

Please refer to the Notes section for the formal definition of a simple cycle

## Input Format
The first and only line contains a single integer $$$n$$$ ($$$3 \le n \le 10^6$$$).

## Output Format
Output a single integer $$$0 \leq x < 10^9+7$$$, the number of cyclic permutations of length $$$n$$$ modulo $$$10^9+7$$$.

## Examples
```input
4
```
```output
16
```
-----
```input
583291
```
```output
135712853
```

## Note
There are $$$16$$$ cyclic permutations for $$$n = 4$$$. $$$[4,2,1,3]$$$ is one such permutation, having a cycle of length four: $$$4 \rightarrow 3 \rightarrow 2 \rightarrow 1 \rightarrow 4$$$.

Nodes $$$v_1$$$, $$$v_2$$$, $$$\ldots$$$, $$$v_k$$$ form a simple cycle if the following conditions hold:

- $$$k \geq 3$$$.
- $$$v_i \neq v_j$$$ for any pair of indices $$$i$$$ and $$$j$$$. ($$$1 \leq i < j \leq k$$$)
- $$$v_i$$$ and $$$v_{i+1}$$$ share an edge for all $$$i$$$ ($$$1 \leq i < k$$$), and $$$v_1$$$ and $$$v_k$$$ share an edge.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
A binary matrix is called good if every even length square sub-matrix has an odd number of ones.

Given a binary matrix $$$a$$$ consisting of $$$n$$$ rows and $$$m$$$ columns, determine the minimum number of cells you need to change to make it good, or report that there is no way to make it good at all.

All the terms above have their usual meanings — refer to the Notes section for their formal definitions.

## Input Format
The first line of input contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \leq m \leq 10^6$$$ and $$$n\cdot m \leq 10^6$$$)  — the number of rows and columns in $$$a$$$, respectively.

The following $$$n$$$ lines each contain $$$m$$$ characters, each of which is one of 0 and 1. If the $$$j$$$-th character on the $$$i$$$-th line is 1, then $$$a_{i,j} = 1$$$. Similarly, if the $$$j$$$-th character on the $$$i$$$-th line is 0, then $$$a_{i,j} = 0$$$.

## Output Format
Output the minimum number of cells you need to change to make $$$a$$$ good, or output $$$-1$$$ if it's not possible at all.

## Examples
```input
3 3
101
001
110
```
```output
2
```
-----
```input
7 15
000100001010010
100111010110001
101101111100100
010000111111010
111010010100001
000011001111101
111111011010011
```
```output
-1
```

## Note
In the first case, changing $$$a_{1,1}$$$ to $$$0$$$ and $$$a_{2,2}$$$ to $$$1$$$ is enough.

You can verify that there is no way to make the matrix in the second case good.

Some definitions —

- A binary matrix is one in which every element is either $$$1$$$ or $$$0$$$.
- A sub-matrix is described by $$$4$$$ parameters — $$$r_1$$$, $$$r_2$$$, $$$c_1$$$, and $$$c_2$$$; here, $$$1 \leq r_1 \leq r_2 \leq n$$$ and $$$1 \leq c_1 \leq c_2 \leq m$$$.
- This sub-matrix contains all elements $$$a_{i,j}$$$ that satisfy both $$$r_1 \leq i \leq r_2$$$ and $$$c_1 \leq j \leq c_2$$$.
- A sub-matrix is, further, called an even length square if $$$r_2-r_1 = c_2-c_1$$$ and $$$r_2-r_1+1$$$ is divisible by $$$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: 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 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: 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.
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
Boboniu likes bit operations. He wants to play a game with you.

Boboniu gives you two sequences of non-negative integers $$$a_1,a_2,\ldots,a_n$$$ and $$$b_1,b_2,\ldots,b_m$$$.

For each $$$i$$$ ($$$1\le i\le n$$$), you're asked to choose a $$$j$$$ ($$$1\le j\le m$$$) and let $$$c_i=a_i\& b_j$$$, where $$$\&$$$ denotes the bitwise AND operation. Note that you can pick the same $$$j$$$ for different $$$i$$$'s.

Find the minimum possible $$$c_1 | c_2 | \ldots | c_n$$$, where $$$|$$$ denotes the bitwise OR operation.

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1\le n,m\le 200$$$).

The next line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$0\le a_i < 2^9$$$).

The next line contains $$$m$$$ integers $$$b_1,b_2,\ldots,b_m$$$ ($$$0\le b_i < 2^9$$$).

## Output Format
Print one integer: the minimum possible $$$c_1 | c_2 | \ldots | c_n$$$.

## Examples
```input
4 2
2 6 4 0
2 4
```
```output
2
```
-----
```input
7 6
1 9 1 9 8 1 0
1 1 4 5 1 4
```
```output
0
```
-----
```input
8 5
179 261 432 162 82 43 10 38
379 357 202 184 197
```
```output
147
```

## Note
For the first example, we have $$$c_1=a_1\& b_2=0$$$, $$$c_2=a_2\& b_1=2$$$, $$$c_3=a_3\& b_1=0$$$, $$$c_4 = a_4\& b_1=0$$$.Thus $$$c_1 | c_2 | c_3 |c_4 =2$$$, and this is the minimal answer we can get.

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
We have a point $$$A$$$ with coordinate $$$x = n$$$ on $$$OX$$$-axis. We'd like to find an integer point $$$B$$$ (also on $$$OX$$$-axis), such that the absolute difference between the distance from $$$O$$$ to $$$B$$$ and the distance from $$$A$$$ to $$$B$$$ is equal to $$$k$$$.

The description of the first test case.

Since sometimes it's impossible to find such point $$$B$$$, we can, in one step, increase or decrease the coordinate of $$$A$$$ by $$$1$$$. What is the minimum number of steps we should do to make such point $$$B$$$ exist?

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

The only line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$0 \le n, k \le 10^6$$$) — the initial position of point $$$A$$$ and desirable absolute difference.

## Output Format
For each test case, print the minimum number of steps to make point $$$B$$$ exist.

## Examples
```input
6
4 0
5 8
0 1000000
0 0
1 0
1000000 1000000
```
```output
0
3
1000000
0
1
0
```

## Note
In the first test case (picture above), if we set the coordinate of $$$B$$$ as $$$2$$$ then the absolute difference will be equal to $$$|(2 - 0) - (4 - 2)| = 0$$$ and we don't have to move $$$A$$$. So the answer is $$$0$$$.

In the second test case, we can increase the coordinate of $$$A$$$ by $$$3$$$ and set the coordinate of $$$B$$$ as $$$0$$$ or $$$8$$$. The absolute difference will be equal to $$$|8 - 0| = 8$$$, so the answer is $$$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
You are given two sequences $$$a_1, a_2, \dots, a_n$$$ and $$$b_1, b_2, \dots, b_n$$$. Each element of both sequences is either $$$0$$$, $$$1$$$ or $$$2$$$. The number of elements $$$0$$$, $$$1$$$, $$$2$$$ in the sequence $$$a$$$ is $$$x_1$$$, $$$y_1$$$, $$$z_1$$$ respectively, and the number of elements $$$0$$$, $$$1$$$, $$$2$$$ in the sequence $$$b$$$ is $$$x_2$$$, $$$y_2$$$, $$$z_2$$$ respectively.

You can rearrange the elements in both sequences $$$a$$$ and $$$b$$$ however you like. After that, let's define a sequence $$$c$$$ as follows:

$$$c_i = \begin{cases} a_i b_i & \mbox{if }a_i > b_i \\ 0 & \mbox{if }a_i = b_i \\ -a_i b_i & \mbox{if }a_i < b_i \end{cases}$$$

You'd like to make $$$\sum_{i=1}^n c_i$$$ (the sum of all elements of the sequence $$$c$$$) as large as possible. What is the maximum possible sum?

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

Each test case consists of two lines. The first line of each test case contains three integers $$$x_1$$$, $$$y_1$$$, $$$z_1$$$ ($$$0 \le x_1, y_1, z_1 \le 10^8$$$) — the number of $$$0$$$-s, $$$1$$$-s and $$$2$$$-s in the sequence $$$a$$$.

The second line of each test case also contains three integers $$$x_2$$$, $$$y_2$$$, $$$z_2$$$ ($$$0 \le x_2, y_2, z_2 \le 10^8$$$; $$$x_1 + y_1 + z_1 = x_2 + y_2 + z_2 > 0$$$) — the number of $$$0$$$-s, $$$1$$$-s and $$$2$$$-s in the sequence $$$b$$$.

## Output Format
For each test case, print the maximum possible sum of the sequence $$$c$$$.

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

## Note
In the first sample, one of the optimal solutions is:

$$$a = \{2, 0, 1, 1, 0, 2, 1\}$$$

$$$b = \{1, 0, 1, 0, 2, 1, 0\}$$$

$$$c = \{2, 0, 0, 0, 0, 2, 0\}$$$

In the second sample, one of the optimal solutions is:

$$$a = \{0, 2, 0, 0, 0\}$$$

$$$b = \{1, 1, 0, 1, 0\}$$$

$$$c = \{0, 2, 0, 0, 0\}$$$

In the third sample, the only possible solution is:

$$$a = \{2\}$$$

$$$b = \{2\}$$$

$$$c = \{0\}$$$

Now solve the problem and return the code.