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

# Problem
Chaneka, a gamer kid, invented a new gaming controller called joyboard. Interestingly, the joyboard she invented can only be used to play one game.

The joyboard has a screen containing $$$n+1$$$ slots numbered from $$$1$$$ to $$$n+1$$$ from left to right. The $$$n+1$$$ slots are going to be filled with an array of non-negative integers $$$[a_1,a_2,a_3,\ldots,a_{n+1}]$$$. Chaneka, as the player, must assign $$$a_{n+1}$$$ with an integer between $$$0$$$ and $$$m$$$ inclusive. Then, for each $$$i$$$ from $$$n$$$ to $$$1$$$, the value of $$$a_i$$$ will be equal to the remainder of dividing $$$a_{i+1}$$$ (the adjacent value to the right) by $$$i$$$. In other words, $$$a_i = a_{i + 1} \bmod i$$$.

Chaneka wants it such that after every slot is assigned with an integer, there are exactly $$$k$$$ distinct values in the entire screen (among all $$$n+1$$$ slots). How many valid ways are there for assigning a non-negative integer into slot $$$n+1$$$?

## Input Format
Each test contains multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 2\cdot10^4$$$) — the number of test cases. The following lines contain the description of each test case.

The only line of each test case contains three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$1 \leq n \leq 10^9$$$; $$$0 \leq m \leq 10^9$$$; $$$1 \leq k \leq n+1$$$) — there are $$$n+1$$$ slots, the integer assigned in slot $$$n+1$$$ must not be bigger than $$$m$$$, and there should be exactly $$$k$$$ distinct values.

## Output Format
For each test case, output a line containing an integer representing the number of valid ways for assigning a non-negative integer into slot $$$n+1$$$.

## Examples
```input
4
4 6 3
2 0 1
265 265 265
3 10 2
```
```output
2
1
0
5
```

## Note
In the first test case, one of the $$$2$$$ possible ways for Chaneka is to choose $$$a_{n+1}=6$$$. If she does that, then:

- $$$a_4=a_5\bmod 4=6\bmod 4=2$$$
- $$$a_3=a_4\bmod 3=2\bmod 3=2$$$
- $$$a_2=a_3\bmod 2=2\bmod 2=0$$$
- $$$a_1=a_2\bmod 1=0\bmod 1=0$$$
- $$$a = [0, 0, 2, 2, 6]$$$
- There are $$$3$$$ distinct values.

In the second test case, the $$$1$$$ possible way for Chaneka is to choose $$$a_{n+1}=0$$$. If she does that, then $$$a = [0, 0, 0]$$$. There is only $$$1$$$ distinct value.

In the third test case, there is no possible way for assigning a non-negative integer into slot $$$n+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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You are given a sequence $$$a_{1}, a_{2}, \ldots, a_{n}$$$. A sequence $$$b_{1}, b_{2}, \ldots, b_{n}$$$ is called good, if it satisfies all of the following conditions:

- $$$b_{i}$$$ is a positive integer for $$$i = 1, 2, \ldots, n$$$;
- $$$b_{i} \neq a_{i}$$$ for $$$i = 1, 2, \ldots, n$$$;
- $$$b_{1} < b_{2} < \ldots < b_{n}$$$.

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 100$$$).

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

## Output Format
For each test case, print a single integer — the minimum value of $$$b_{n}$$$ among all good sequences $$$b$$$.

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

## Note
In the first test case, $$$b = [2, 4, 5, 7, 8]$$$ is a good sequence. It can be proved that there is no good $$$b$$$ with $$$b_{5} < 8$$$.

In the second test case, $$$b = [1, 2, 3, 4]$$$ is an optimal good sequence.

In the third test case, $$$b = [2]$$$ is an optimal good sequence.

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 have $$$n$$$ sets of integers $$$S_{1}, S_{2}, \ldots, S_{n}$$$. We call a set $$$S$$$ attainable, if it is possible to choose some (possibly, none) of the sets $$$S_{1}, S_{2}, \ldots, S_{n}$$$ so that $$$S$$$ is equal to their union$$$^{\dagger}$$$. If you choose none of $$$S_{1}, S_{2}, \ldots, S_{n}$$$, their union is an empty set.

Find the maximum number of elements in an attainable $$$S$$$ such that $$$S \neq S_{1} \cup S_{2} \cup \ldots \cup S_{n}$$$.

$$$^{\dagger}$$$ The union of sets $$$A_1, A_2, \ldots, A_k$$$ is defined as the set of elements present in at least one of these sets. It is denoted by $$$A_1 \cup A_2 \cup \ldots \cup A_k$$$. For example, $$$\{2, 4, 6\} \cup \{2, 3\} \cup \{3, 6, 7\} = \{2, 3, 4, 6, 7\}$$$.

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 50$$$).

The following $$$n$$$ lines describe the sets $$$S_1, S_2, \ldots, S_n$$$. The $$$i$$$-th of these lines contains an integer $$$k_{i}$$$ ($$$1 \le k_{i} \le 50$$$) — the number of elements in $$$S_{i}$$$, followed by $$$k_{i}$$$ integers $$$s_{i, 1}, s_{i, 2}, \ldots, s_{i, k_{i}}$$$ ($$$1 \le s_{i, 1} < s_{i, 2} < \ldots < s_{i, k_{i}} \le 50$$$) — the elements of $$$S_{i}$$$.

## Output Format
For each test case, print a single integer — the maximum number of elements in an attainable $$$S$$$ such that $$$S \neq S_{1} \cup S_{2} \cup \ldots \cup S_{n}$$$.

## Examples
```input
4
3
3 1 2 3
2 4 5
2 3 4
4
4 1 2 3 4
3 2 5 6
3 3 5 6
3 4 5 6
5
1 1
3 3 6 10
1 9
2 1 3
3 5 8 9
1
2 4 28
```
```output
4
5
6
0
```

## Note
In the first test case, $$$S = S_{1} \cup S_{3} = \{1, 2, 3, 4\}$$$ is the largest attainable set not equal to $$$S_1 \cup S_2 \cup S_3 = \{1, 2, 3, 4, 5\}$$$.

In the second test case, we can pick $$$S = S_{2} \cup S_{3} \cup S_{4} = \{2, 3, 4, 5, 6\}$$$.

In the third test case, we can pick $$$S = S_{2} \cup S_{5} = S_{2} \cup S_{3} \cup S_{5} = \{3, 5, 6, 8, 9, 10\}$$$.

In the fourth test case, the only attainable set is $$$S = \varnothing$$$.

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
Monocarp has an integer $$$n$$$.

He wants to represent his number as a sum of three distinct positive integers $$$x$$$, $$$y$$$, and $$$z$$$. Additionally, Monocarp wants none of the numbers $$$x$$$, $$$y$$$, and $$$z$$$ to be divisible by $$$3$$$.

Your task is to help Monocarp to find any valid triplet of distinct positive integers $$$x$$$, $$$y$$$, and $$$z$$$, or report that such a triplet does not exist.

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

The only line of each testcase contains a single integer $$$n$$$ ($$$1 \le n \le 10^{9}$$$).

## Output Format
For each testcase, if there is no valid triplet $$$x$$$, $$$y$$$, and $$$z$$$, print NO on the first line.

Otherwise, print YES on the first line. On the second line, print any valid triplet of distinct positive integers $$$x$$$, $$$y$$$, and $$$z$$$ such that $$$x + y + z = n$$$, and none of the printed numbers are divisible by $$$3$$$. If there are multiple valid triplets, you can print any of them.

## Examples
```input
4
10
4
15
9
```
```output
YES
4 5 1
NO
YES
2 8 5
NO
```

## Note
In the first testcase, one of the valid triplets is $$$x = 4$$$, $$$y = 5$$$, $$$z = 1$$$. None of these numbers are divisible by three, and $$$4 + 5 + 1 = 10$$$.

In the second testcase, there is no valid triplet.

In the third testcase, one of the valid triplets is $$$x = 2$$$, $$$y = 8$$$, $$$z = 5$$$. None of these numbers are divisible by three, and $$$2 + 8 + 5 = 15$$$.

In the fourth testcase, there is no valid triplet.

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
Monocarp is a team leader in a massive IT company.

There are $$$m$$$ projects his team of programmers has to complete, numbered from $$$1$$$ to $$$m$$$. The $$$i$$$-th project has a difficulty level $$$b_i$$$.

There are $$$n$$$ programmers in the team, numbered from $$$1$$$ to $$$n$$$. The $$$j$$$-th programmer has a stress tolerance level $$$a_j$$$.

Monocarp wants to assign the programmers to the projects in such a way that:

- each programmer is assigned to no more than one project;
- each project has at least one programmer assigned to it;
- let $$$k$$$ programmers be assigned to the $$$i$$$-th project; then all the assigned programmers have to have a stress tolerance level greater than or equal to $$$\frac{b_i}{k}$$$.

Help Monocarp to find a valid assignment. If there are multiple answers, print any of them.

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 2 \cdot 10^5$$$; $$$1 \le m \le 20$$$) — the number of programmers and the number of projects.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the stress tolerance level of each programmer.

The third line contains $$$m$$$ integers $$$b_1, b_2, \dots, b_m$$$ ($$$1 \le b_i \le 10^9$$$) — the difficulty level of each project.

## Output Format
If there is no valid assignment, print "NO".

Otherwise, in the first line, print "YES". In the $$$i$$$-th of the next $$$m$$$ lines, print the list of the programmers assigned to the $$$i$$$-th project: first, the number of programmers, then their indices in an arbitrary order.

If there are multiple answers, print any of them.

## Examples
```input
5 3
4 6 100 5 1
50 1 12
```
```output
YES
1 3
1 5
3 2 4 1
```
-----
```input
5 3
3 6 100 5 1
50 1 12
```
```output
NO
```
-----
```input
5 3
2 2 2 2 4
3 5 1
```
```output
YES
1 5
3 1 2 3
1 4
```
-----
```input
5 1
10 20 30 40 50
4
```
```output
YES
1 4
```

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

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

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

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Monocarp is the most famous thief in Berland. This time, he decided to steal two diamonds. Unfortunately for Monocarp, there are $$$n$$$ cameras monitoring the diamonds. Each camera has two parameters, $$$t_i$$$ and $$$s_i$$$. The first parameter determines whether the camera is monitoring the first diamond only ($$$t_i=1$$$), the second diamond only ($$$t_i=2$$$), or both diamonds ($$$t_i=3$$$). The second parameter determines the number of seconds the camera will be disabled after it is hacked.

Every second, Monocarp can perform one of the following three actions:

- do nothing;
- choose a camera and hack it; if Monocarp hacks the $$$i$$$-th camera, it will be disabled for the next $$$s_i$$$ seconds (if the current second is the $$$T$$$-th one, the camera will be disabled from the $$$(T+1)$$$-th to the $$$(T+s_i)$$$-th second, inclusive);
- steal a diamond if all cameras monitoring it are currently disabled. Monocarp cannot steal the second diamond if he hasn't stolen the first diamond yet.

Note that Monocarp can hack a camera multiple times, even if it is currently disabled.

Your task is to determine the minimum time it will take Monocarp to steal both diamonds, beginning with the first diamond, or report that it is impossible.

## Input Format
The first line contains a single integer $$$n$$$ ($$$0 \le n \le 1500$$$) — the number of cameras.

Then $$$n$$$ lines follow, the $$$i$$$-th of them contains two integers $$$t_i$$$ and $$$s_i$$$ ($$$1 \le t_i \le 3$$$; $$$1 \le s_i \le 2n$$$) — the parameters of the $$$i$$$-th camera.

## Output Format
Print a single integer — the minimum time it will take for Monocarp to steal the first diamond first and then the second diamond. If it is impossible, print -1.

## Examples
```input
4
2 6
1 2
1 2
2 1
```
```output
6
```
-----
```input
4
2 8
3 2
3 2
3 5
```
```output
9
```
-----
```input
2
3 2
2 3
```
```output
4
```
-----
```input
1
3 1
```
```output
4
```
-----
```input
8
2 1
2 2
3 5
3 6
1 2
1 3
1 4
1 5
```
```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
Monocarp is a great solver of adhoc problems. Recently, he participated in an Educational Codeforces Round, and gained rating!

Monocarp knew that, before the round, his rating was $$$a$$$. After the round, it increased to $$$b$$$ ($$$b > a$$$). He wrote both values one after another to not forget them.

However, he wrote them so close to each other, that he can't tell now where the first value ends and the second value starts.

Please, help him find some values $$$a$$$ and $$$b$$$ such that:

- neither of them has a leading zero;
- both of them are strictly greater than $$$0$$$;
- $$$b > a$$$;
- they produce the given value $$$ab$$$ when written one after another.

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

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

The only line of each testcase consists of a single string $$$ab$$$ of length from $$$2$$$ to $$$8$$$ that:

- consists only of digits;
- doesn't start with a zero.

## Output Format
For each testcase, determine if such values $$$a$$$ and $$$b$$$ exist. If they don't, print -1. Otherwise, print two integers $$$a$$$ and $$$b$$$.

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

## Examples
```input
5
20002001
391125
200200
2001000
12
```
```output
2000 2001
39 1125
-1
200 1000
1 2
```

## Note
In the second testcase, printing $$$3$$$ and $$$91125$$$ is also valid.

In the third testcase, $$$20$$$ and $$$0200$$$ is not valid, because $$$b$$$ has a leading zero. $$$200$$$ and $$$200$$$ is not valid, because $$$200$$$ is not strictly greater than $$$200$$$.

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
You are given a binary string $$$s$$$ (a string consisting only of 0-s and 1-s).

You can perform two types of operations on $$$s$$$:

1. delete one character from $$$s$$$. This operation costs $$$1$$$ coin;
2. swap any pair of characters in $$$s$$$. This operation is free (costs $$$0$$$ coins).

You can perform these operations any number of times and in any order.

Let's name a string you've got after performing operations above as $$$t$$$. The string $$$t$$$ is good if for each $$$i$$$ from $$$1$$$ to $$$|t|$$$ $$$t_i \neq s_i$$$ ($$$|t|$$$ is the length of the string $$$t$$$). The empty string is always good. Note that you are comparing the resulting string $$$t$$$ with the initial string $$$s$$$.

What is the minimum total cost to make the string $$$t$$$ good?

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

The only line of each test case contains a binary string $$$s$$$ ($$$1 \le |s| \le 2 \cdot 10^5$$$; $$$s_i \in \{$$$0, 1$$$\}$$$) — the initial string, consisting of characters 0 and/or 1.

Additional constraint on the input: the total length of all strings $$$s$$$ doesn't exceed $$$2 \cdot 10^5$$$.

## Output Format
For each test case, print one integer — the minimum total cost to make string $$$t$$$ good.

## Examples
```input
4
0
011
0101110001
111100
```
```output
1
1
0
4
```

## Note
In the first test case, you have to delete a character from $$$s$$$ to get the empty string $$$t$$$. Only then $$$t$$$ becomes good. One deletion costs $$$1$$$ coin.

In the second test case, you can, for example, delete the second character from $$$s$$$ to get the string 01, and then swap the first and second characters to get the string $$$t$$$ $$$=$$$ 10. String $$$t$$$ is good, since $$$t_1 \neq s_1$$$ and $$$t_2 \neq s_2$$$. The total cost is $$$1$$$ coin.

In the third test case, you can, for example, swap $$$s_1$$$ with $$$s_2$$$, swap $$$s_3$$$ with $$$s_4$$$, swap $$$s_5$$$ with $$$s_7$$$, $$$s_6$$$ with $$$s_8$$$ and $$$s_9$$$ with $$$s_{10}$$$. You'll get $$$t$$$ $$$=$$$ 1010001110. All swap operations are free, so the total cost is $$$0$$$.

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

# Problem
In this problem, you are initially given an empty multiset. You have to process two types of queries:

1. ADD $$$x$$$ — add an element equal to $$$2^{x}$$$ to the multiset;
2. GET $$$w$$$ — say whether it is possible to take the sum of some subset of the current multiset and get a value equal to $$$w$$$.

## Input Format
The first line contains one integer $$$m$$$ ($$$1 \le m \le 10^5$$$) — the number of queries.

Then $$$m$$$ lines follow, each of which contains two integers $$$t_i$$$, $$$v_i$$$, denoting the $$$i$$$-th query. If $$$t_i = 1$$$, then the $$$i$$$-th query is ADD $$$v_i$$$ ($$$0 \le v_i \le 29$$$). If $$$t_i = 2$$$, then the $$$i$$$-th query is GET $$$v_i$$$ ($$$0 \le v_i \le 10^9$$$).

## Output Format
For each GET query, print YES if it is possible to choose a subset with sum equal to $$$w$$$, or NO if it is impossible.

## Examples
```input
5
1 0
1 0
1 0
2 3
2 4
```
```output
YES
NO
```
-----
```input
7
1 0
1 1
1 2
1 10
2 4
2 6
2 7
```
```output
YES
YES
YES
```

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 $$$[p_1, p_2, \dots, p_n]$$$, where all elements are distinct.

You can perform several (possibly zero) operations with it. In one operation, you can choose a contiguous subsegment of $$$p$$$ and remove all elements from that subsegment, except for the minimum element on that subsegment. For example, if $$$p = [3, 1, 4, 7, 5, 2, 6]$$$ and you choose the subsegment from the $$$3$$$-rd element to the $$$6$$$-th element, the resulting array is $$$[3, 1, 2, 6]$$$.

An array $$$a$$$ is called reachable if it can be obtained from $$$p$$$ using several (maybe zero) aforementioned operations. Calculate the number of reachable arrays, and print it modulo $$$998244353$$$.

## Input Format
The first line of the input 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 contains one integer $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$). The second line contains $$$n$$$ distinct integers $$$p_1, p_2, \dots, p_n$$$ ($$$1 \le p_i \le 10^9$$$).

Additional constraint on the input: the sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.

## Output Format
For each test case, print one integer — the number of reachable arrays, taken modulo $$$998244353$$$.

## Examples
```input
3
2
2 1
4
2 4 1 3
5
10 2 6 3 4
```
```output
2
6
12
```

Now solve the problem and return the code.