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

# Problem
You are given an array $$$a$$$ of length $$$n$$$ consisting of non-negative integers.

You have to calculate the value of $$$\sum_{l=1}^{n} \sum_{r=l}^{n} f(l, r) \cdot (r - l + 1)$$$, where $$$f(l, r)$$$ is $$$a_l \oplus a_{l+1} \oplus \dots \oplus a_{r-1} \oplus a_r$$$ (the character $$$\oplus$$$ denotes bitwise XOR).

Since the answer can be very large, print it modulo $$$998244353$$$.

## Input Format
The first line contains one integer $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — the length of the array $$$a$$$.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^9)$$$.

## Output Format
Print the one integer — the value of $$$\sum_{l=1}^{n} \sum_{r=l}^{n} f(l, r) \cdot (r - l + 1)$$$, taken modulo $$$998244353$$$.

## Examples
```input
3
1 3 2
```
```output
12
```
-----
```input
4
39 68 31 80
```
```output
1337
```
-----
```input
7
313539461 779847196 221612534 488613315 633203958 394620685 761188160
```
```output
257421502
```

## Note
In the first example, the answer is equal to $$$f(1, 1) + 2 \cdot f(1, 2) + 3 \cdot f(1, 3) + f(2, 2) + 2 \cdot f(2, 3) + f(3, 3) = $$$ $$$= 1 + 2 \cdot 2 + 3 \cdot 0 + 3 + 2 \cdot 1 + 2 = 12$$$.

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

# Problem
An array $$$b_1, b_2, \ldots, b_n$$$ of positive integers is good if all the sums of two adjacent elements are equal to the same value. More formally, the array is good if there exists a $$$k$$$ such that $$$b_1 + b_2 = b_2 + b_3 = \ldots = b_{n-1} + b_n = k$$$.

Doremy has an array $$$a$$$ of length $$$n$$$. Now Doremy can permute its elements (change their order) however she wants. Determine if she can make the array good.

## Input Format
The input consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1\le t\le 100$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 100$$$) — the length of the array $$$a$$$.

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

There are no constraints on the sum of $$$n$$$ over all test cases.

## Output Format
For each test case, print "Yes" (without quotes), if it is possible to make the array good, and "No" (without quotes) otherwise.

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

## Examples
```input
5
2
8 9
3
1 1 2
4
1 1 4 5
5
2 3 3 3 3
4
100000 100000 100000 100000
```
```output
Yes
Yes
No
No
Yes
```

## Note
In the first test case, $$$[8,9]$$$ and $$$[9,8]$$$ are good.

In the second test case, $$$[1,2,1]$$$ is good because $$$a_1+a_2=a_2+a_3=3$$$.

In the third test case, it can be shown that no permutation is 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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
Qingshan has a string $$$s$$$, while Daniel has a string $$$t$$$. Both strings only contain $$$\texttt{0}$$$ and $$$\texttt{1}$$$.

A string $$$a$$$ of length $$$k$$$ is good if and only if

- $$$a_i \ne a_{i+1}$$$ for all $$$i=1,2,\ldots,k-1$$$.

For example, $$$\texttt{1}$$$, $$$\texttt{101}$$$, $$$\texttt{0101}$$$ are good, while $$$\texttt{11}$$$, $$$\texttt{1001}$$$, $$$\texttt{001100}$$$ are not good.

Qingshan wants to make $$$s$$$ good. To do this, she can do the following operation any number of times (possibly, zero):

- insert $$$t$$$ to any position of $$$s$$$ (getting a new $$$s$$$).

Please tell Qingshan if it is possible to make $$$s$$$ good.

## Input Format
The input consists of multiple test cases. The first line contains a single integer $$$T$$$ ($$$1\le T\le 2000$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n,m \le 50$$$) — the length of the strings $$$s$$$ and $$$t$$$, respectively.

The second line of each test case contains a string $$$s$$$ of length $$$n$$$.

The third line of each test case contains a string $$$t$$$ of length $$$m$$$.

It is guaranteed that $$$s$$$ and $$$t$$$ only contain $$$\texttt{0}$$$ and $$$\texttt{1}$$$.

## Output Format
For each test case, print "YES" (without quotes), if it is possible to make $$$s$$$ good, and "NO" (without quotes) otherwise.

You can print letters in any case (upper or lower).

## Examples
```input
5
1 1
1
0
3 3
111
010
3 2
111
00
6 7
101100
1010101
10 2
1001001000
10
```
```output
Yes
Yes
No
No
No
```

## Note
In the first test case, $$$s$$$ is good initially, so you can get a good $$$s$$$ by doing zero operations.

In the second test case, you can do the following two operations (the inserted string $$$t$$$ is underlined):

1. $$$\texttt{1}\underline{\texttt{010}}\texttt{11}$$$
2. $$$\texttt{10101}\underline{\texttt{010}}\texttt{1}$$$

and get $$$s = \texttt{101010101}$$$, which is good.

In the third test case, there is no way to make $$$s$$$ good after any number of operations.

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
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 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 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 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.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 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 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.