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 a circular maze such as the ones shown in the figures.

- Circular walls are described by a radius $$$r$$$, the distance from the center, and two angles $$$\theta_1, \theta_2$$$ describing the beginning and the end of the wall in the clockwise direction. Notice that swapping the two angles changes the wall.
- Straight walls are described by an angle $$$\theta$$$, the direction of the wall, and two radii $$$r_1 < r_2$$$ describing the beginning and the end of the wall.

Angles are measured in degrees; the angle $$$0$$$ corresponds to the upward pointing direction; and angles increase clockwise (hence the east direction corresponds to the angle $$$90$$$).

## Input Format
Each test contains multiple test cases. The first line contains an integer $$$t$$$ ($$$1\le t\le 20$$$) — the number of test cases. The descriptions of the $$$t$$$ test cases follow.

The first line of each test case contains an integer $$$n$$$ ($$$1 \leq n \leq 5000$$$) — the number of walls.

Each of the following $$$n$$$ lines each contains a character (C for circular, and S for straight) and three integers:

- either $$$r, \theta_1, \theta_2$$$ ($$$1 \leq r \leq 20$$$ and $$$0 \leq \theta_1,\theta_2 < 360$$$ with $$$\theta_1 \neq \theta_2$$$) if the wall is circular,
- or $$$r_1$$$, $$$r_2$$$ and $$$\theta$$$ ($$$1 \leq r_1 < r_2 \leq 20$$$ and $$$0 \leq \theta < 360$$$) if the wall is straight.

It is guaranteed that circular walls do not overlap (but two circular walls may intersect at one or two points), and that straight walls do not overlap (but two straight walls may intersect at one point). However, circular and straight walls can intersect arbitrarily.

## Output Format
For each test case, print YES if the maze can be solved and NO otherwise.

## Examples
```input
2
5
C 1 180 90
C 5 250 230
C 10 150 140
C 20 185 180
S 1 20 180
6
C 1 180 90
C 5 250 230
C 10 150 140
C 20 185 180
S 1 20 180
S 5 10 0
```
```output
YES
NO
```

## Note
The two sample test cases correspond to the two mazes in the picture.

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
Petya and Vasya are brothers. Today is a special day for them as their parents left them home alone and commissioned them to do n chores. Each chore is characterized by a single parameter — its complexity. The complexity of the i-th chore equals hi.

As Petya is older, he wants to take the chores with complexity larger than some value x (hi > x) to leave to Vasya the chores with complexity less than or equal to x (hi ≤ x). The brothers have already decided that Petya will do exactly a chores and Vasya will do exactly b chores (a + b = n).

In how many ways can they choose an integer x so that Petya got exactly a chores and Vasya got exactly b chores?

## Input Format
The first input line contains three integers n, a and b (2 ≤ n ≤ 2000; a, b ≥ 1; a + b = n) — the total number of chores, the number of Petya's chores and the number of Vasya's chores.

The next line contains a sequence of integers h1, h2, ..., hn (1 ≤ hi ≤ 109), hi is the complexity of the i-th chore. The numbers in the given sequence are not necessarily different.

All numbers on the lines are separated by single spaces.

## Output Format
Print the required number of ways to choose an integer value of x. If there are no such ways, print 0.

## Examples
```input
5 2 3
6 2 3 100 1
```
```output
3
```
-----
```input
7 3 4
1 1 9 1 1 1 1
```
```output
0
```

## Note
In the first sample the possible values of x are 3, 4 or 5.

In the second sample it is impossible to find such x, that Petya got 3 chores and Vasya got 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
You are given an integer a that consists of n digits. You are also given a sequence of digits s of length m. The digit in position j (1 ≤ j ≤ m) of sequence s means that you can choose an arbitrary position i (1 ≤ i ≤ n) in a and replace the digit in the chosen position i with sj. Each element in the sequence s can participate in no more than one replacing operation.

Your task is to perform such sequence of replacements, that the given number a gets maximum value. You are allowed to use not all elements from s.

## Input Format
The first line contains positive integer a. Its length n is positive and doesn't exceed 105. The second line contains sequence of digits s. Its length m is positive and doesn't exceed 105. The digits in the sequence s are written consecutively without any separators.

The given number a doesn't contain leading zeroes.

## Output Format
Print the maximum value that can be obtained from a after a series of replacements. You are allowed to use not all elements from s. The printed number shouldn't contain any leading zeroes.

## Examples
```input
1024
010
```
```output
1124
```
-----
```input
987
1234567
```
```output
987
```

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
Yeri has an array of $$$n + 2$$$ non-negative integers : $$$a_0, a_1, ..., a_n, a_{n + 1}$$$.

We know that $$$a_0 = a_{n + 1} = 0$$$.

She wants to make all the elements of $$$a$$$ equal to zero in the minimum number of operations.

In one operation she can do one of the following:

- Choose the leftmost maximum element and change it to the maximum of the elements on its left.
- Choose the rightmost maximum element and change it to the maximum of the elements on its right.

Help her find the minimum number of operations needed to make all elements of $$$a$$$ equal to zero.

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

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le n$$$).

## Output Format
Print a single integer  — the minimum number of operations needed to make all elements of $$$a$$$ equal to zero.

## Examples
```input
6
1 4 2 4 0 2
```
```output
7
```
-----
```input
5
1 3 5 4 2
```
```output
9
```
-----
```input
4
0 0 0 0
```
```output
0
```

## Note
In the first sample, you get $$$\langle 1, \underline{1}, 2, 4, 0, 2 \rangle$$$ by performing the first operation and $$$\langle 1, 4, 2, \underline{2}, 0, 2 \rangle$$$ by performing the second operation.

One way to achieve our goal is shown below. (The underlines show the last change.) $$$\langle 1, 4, 2, 4, 0, 2 \rangle \to \langle 1, 4, 2, \underline{2}, 0, 2 \rangle \to \langle 1, \underline{1}, 2, 2, 0, 2 \rangle \to \langle 1, 1, 2, 2, 0, \underline{0} \rangle \to \langle 1, 1, 2, \underline{0}, 0, 0 \rangle \to \langle 1, 1, \underline{0}, 0, 0, 0 \rangle \to \langle \underline{0}, 1, 0, 0, 0, 0 \rangle \to \langle 0, \underline{0}, 0, 0, 0, 0 \rangle $$$

In the third sample each element is already equal to zero so no operations are needed.

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 a binary string $$$S$$$ of length $$$n$$$ indexed from $$$1$$$ to $$$n$$$. You can perform the following operation any number of times (possibly zero):

- Choose two integers $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le n$$$). Let $$$cnt_0$$$ be the number of times 0 occurs in $$$S[l \ldots r]$$$ and $$$cnt_1$$$ be the number of times 1 occurs in $$$S[l \ldots r]$$$. You can pay $$$|cnt_0 - cnt_1| + 1$$$ coins and sort the $$$S[l \ldots r]$$$. (by $$$S[l \ldots r]$$$ we mean the substring of $$$S$$$ starting at position $$$l$$$ and ending at position $$$r$$$)For example if $$$S = $$$ 11001, we can perform the operation on $$$S[2 \ldots 4]$$$, paying $$$|2 - 1| + 1 = 2$$$ coins, and obtain $$$S = $$$ 10011 as a new string.

Find the minimum total number of coins required to sort $$$S$$$ in increasing order.

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

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the size of $$$S$$$.

The second line of each test case contains a binary string $$$S$$$ of $$$n$$$ characters $$$S_1S_2 \ldots S_n$$$. ($$$S_i = $$$ 0 or $$$S_i = $$$ 1 for each $$$1 \le i \le n$$$)

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

## Output Format
For each test case, output the minimum total number of coins required to sort $$$S$$$ in increasing order.

## Examples
```input
7
1
1
2
10
3
101
4
1000
5
11010
6
110000
20
01000010001010011000
```
```output
0
1
1
3
2
2
5
```

## Note
In the first test case, $$$S$$$ is already sorted.

In the second test case, it's enough to apply the operation with $$$l = 1, r = 2$$$.

In the third test case, it's enough to apply the operation with $$$l = 1, r = 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 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 walking through a parkway near your house. The parkway has $$$n+1$$$ benches in a row numbered from $$$1$$$ to $$$n+1$$$ from left to right. The distance between the bench $$$i$$$ and $$$i+1$$$ is $$$a_i$$$ meters.

Initially, you have $$$m$$$ units of energy. To walk $$$1$$$ meter of distance, you spend $$$1$$$ unit of your energy. You can't walk if you have no energy. Also, you can restore your energy by sitting on benches (and this is the only way to restore the energy). When you are sitting, you can restore any integer amount of energy you want (if you sit longer, you restore more energy). Note that the amount of your energy can exceed $$$m$$$.

Your task is to find the minimum amount of energy you have to restore (by sitting on benches) to reach the bench $$$n+1$$$ from the bench $$$1$$$ (and end your walk).

You have to answer $$$t$$$ independent test cases.

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

The first line of the test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 100$$$; $$$1 \le m \le 10^4$$$).

The second line of the test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 100$$$), where $$$a_i$$$ is the distance between benches $$$i$$$ and $$$i+1$$$.

## Output Format
For each test case, print one integer — the minimum amount of energy you have to restore (by sitting on benches) to reach the bench $$$n+1$$$ from the bench $$$1$$$ (and end your walk) in the corresponding test case.

## Examples
```input
3
3 1
1 2 1
4 5
3 3 5 2
5 16
1 2 3 4 5
```
```output
3
8
0
```

## Note
In the first test case of the example, you can walk to the bench $$$2$$$, spending $$$1$$$ unit of energy, then restore $$$2$$$ units of energy on the second bench, walk to the bench $$$3$$$, spending $$$2$$$ units of energy, restore $$$1$$$ unit of energy and go to the bench $$$4$$$.

In the third test case of the example, you have enough energy to just go to the bench $$$6$$$ without sitting at all.

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
The store sells $$$n$$$ items, the price of the $$$i$$$-th item is $$$p_i$$$. The store's management is going to hold a promotion: if a customer purchases at least $$$x$$$ items, $$$y$$$ cheapest of them are free.

The management has not yet decided on the exact values of $$$x$$$ and $$$y$$$. Therefore, they ask you to process $$$q$$$ queries: for the given values of $$$x$$$ and $$$y$$$, determine the maximum total value of items received for free, if a customer makes one purchase.

Note that all queries are independent; they don't affect the store's stock.

## Input Format
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 2 \cdot 10^5$$$) — the number of items in the store and the number of queries, respectively.

The second line contains $$$n$$$ integers $$$p_1, p_2, \dots, p_n$$$ ($$$1 \le p_i \le 10^6$$$), where $$$p_i$$$ — the price of the $$$i$$$-th item.

The following $$$q$$$ lines contain two integers $$$x_i$$$ and $$$y_i$$$ each ($$$1 \le y_i \le x_i \le n$$$) — the values of the parameters $$$x$$$ and $$$y$$$ in the $$$i$$$-th query.

## Output Format
For each query, print a single integer — the maximum total value of items received for free for one purchase.

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

## Note
In the first query, a customer can buy three items worth $$$5, 3, 5$$$, the two cheapest of them are $$$3 + 5 = 8$$$.

In the second query, a customer can buy two items worth $$$5$$$ and $$$5$$$, the cheapest of them is $$$5$$$.

In the third query, a customer has to buy all the items to receive the three cheapest of them for free; their total price is $$$1 + 2 + 3 = 6$$$.

Now solve the problem and return the code.
You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in 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: 3.0 seconds
Memory limit: 512.0 MB

# Problem
You are given $$$n$$$ points on the plane, the coordinates of the $$$i$$$-th point are $$$(x_i, y_i)$$$. No two points have the same coordinates.

The distance between points $$$i$$$ and $$$j$$$ is defined as $$$d(i,j) = |x_i - x_j| + |y_i - y_j|$$$.

For each point, you have to choose a color, represented by an integer from $$$1$$$ to $$$n$$$. For every ordered triple of different points $$$(a,b,c)$$$, the following constraints should be met:

- if $$$a$$$, $$$b$$$ and $$$c$$$ have the same color, then $$$d(a,b) = d(a,c) = d(b,c)$$$;
- if $$$a$$$ and $$$b$$$ have the same color, and the color of $$$c$$$ is different from the color of $$$a$$$, then $$$d(a,b) < d(a,c)$$$ and $$$d(a,b) < d(b,c)$$$.

Calculate the number of different ways to choose the colors that meet these constraints.

## Input Format
The first line contains one integer $$$n$$$ ($$$2 \le n \le 100$$$) — the number of points.

Then $$$n$$$ lines follow. The $$$i$$$-th of them contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$0 \le x_i, y_i \le 10^8$$$).

No two points have the same coordinates (i. e. if $$$i \ne j$$$, then either $$$x_i \ne x_j$$$ or $$$y_i \ne y_j$$$).

## Output Format
Print one integer — the number of ways to choose the colors for the points. Since it can be large, print it modulo $$$998244353$$$.

## Examples
```input
3
1 0
3 0
2 1
```
```output
9
```
-----
```input
5
1 2
2 4
3 4
4 4
1 3
```
```output
240
```
-----
```input
4
1 0
3 0
2 1
2 0
```
```output
24
```

## Note
In the first test, the following ways to choose the colors are suitable:

- $$$[1, 1, 1]$$$;
- $$$[2, 2, 2]$$$;
- $$$[3, 3, 3]$$$;
- $$$[1, 2, 3]$$$;
- $$$[1, 3, 2]$$$;
- $$$[2, 1, 3]$$$;
- $$$[2, 3, 1]$$$;
- $$$[3, 1, 2]$$$;
- $$$[3, 2, 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: 512.0 MB

# Problem
You are asked to build an array $$$a$$$, consisting of $$$n$$$ integers, each element should be from $$$1$$$ to $$$k$$$.

The array should be non-decreasing ($$$a_i \le a_{i+1}$$$ for all $$$i$$$ from $$$1$$$ to $$$n-1$$$).

You are also given additional constraints on it. Each constraint is of one of three following types:

- $$$1~i~x$$$: $$$a_i$$$ should not be equal to $$$x$$$;
- $$$2~i~j~x$$$: $$$a_i + a_j$$$ should be less than or equal to $$$x$$$;
- $$$3~i~j~x$$$: $$$a_i + a_j$$$ should be greater than or equal to $$$x$$$.

Build any non-decreasing array that satisfies all constraints or report that no such array exists.

## 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, m$$$ and $$$k$$$ ($$$2 \le n \le 2 \cdot 10^4$$$; $$$0 \le m \le 2 \cdot 10^4$$$; $$$2 \le k \le 10$$$).

The $$$i$$$-th of the next $$$m$$$ lines contains a description of a constraint. Each constraint is of one of three following types:

- $$$1~i~x$$$ ($$$1 \le i \le n$$$; $$$1 \le x \le k$$$): $$$a_i$$$ should not be equal to $$$x$$$;
- $$$2~i~j~x$$$ ($$$1 \le i < j \le n$$$; $$$2 \le x \le 2 \cdot k$$$): $$$a_i + a_j$$$ should be less than or equal to $$$x$$$;
- $$$3~i~j~x$$$ ($$$1 \le i < j \le n$$$; $$$2 \le x \le 2 \cdot k$$$): $$$a_i + a_j$$$ should be greater than or equal to $$$x$$$.

The sum of $$$n$$$ over all testcases doesn't exceed $$$2 \cdot 10^4$$$. The sum of $$$m$$$ over all testcases doesn't exceed $$$2 \cdot 10^4$$$.

## Output Format
For each testcase, determine if there exists a non-decreasing array that satisfies all conditions. If there is no such array, then print -1. Otherwise, print any valid array — $$$n$$$ integers from $$$1$$$ to $$$k$$$.

## Examples
```input
4
4 0 4
2 2 3
3 1 2 3
1 2 2
3 3 2
1 1 1
2 2 3 2
3 2 3 2
5 5 5
3 2 5 7
2 4 5 10
3 4 5 6
3 3 4 7
2 1 5 7
```
```output
1 2 3 4
1 3
-1
1 2 2 5 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
At the store, the salespeople want to make all prices round.

In this problem, a number that is a power of $$$10$$$ is called a round number. For example, the numbers $$$10^0 = 1$$$, $$$10^1 = 10$$$, $$$10^2 = 100$$$ are round numbers, but $$$20$$$, $$$110$$$ and $$$256$$$ are not round numbers.

So, if an item is worth $$$m$$$ bourles (the value of the item is not greater than $$$10^9$$$), the sellers want to change its value to the nearest round number that is not greater than $$$m$$$. They ask you: by how many bourles should you decrease the value of the item to make it worth exactly $$$10^k$$$ bourles, where the value of $$$k$$$ — is the maximum possible ($$$k$$$ — any non-negative integer).

For example, let the item have a value of $$$178$$$-bourles. Then the new price of the item will be $$$100$$$, and the answer will be $$$178-100=78$$$.

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

Each test case is a string containing a single integer $$$m$$$ ($$$1 \le m \le 10^9$$$) — the price of the item.

## Output Format
For each test case, output on a separate line a single integer $$$d$$$ ($$$0 \le d < m$$$) such that if you reduce the cost of the item by $$$d$$$ bourles, the cost of the item will be the maximal possible round number. More formally: $$$m - d = 10^k$$$, where $$$k$$$ — the maximum possible non-negative integer.

## Examples
```input
7
1
2
178
20
999999999
9000
987654321
```
```output
0
1
78
10
899999999
8000
887654321
```

## Note
In the example:

- $$$1 - 0 = 10^0$$$,
- $$$2 - 1 = 10^0$$$,
- $$$178 - 78 = 10^2$$$,
- $$$20 - 10 = 10^1$$$,
- $$$999999999 - 899999999 = 10^8$$$,
- $$$9000 - 8000 = 10^3$$$,
- $$$987654321 - 887654321 = 10^8$$$.

Note that in each test case, we get the maximum possible round number.

Now solve the problem and return the code.