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
You are given a bracket sequence consisting of $$$n$$$ characters '(' and/or )'. You perform several operations with it.

During one operation, you choose the shortest prefix of this string (some amount of first characters of the string) that is good and remove it from the string.

The prefix is considered good if one of the following two conditions is satisfied:

- this prefix is a regular bracket sequence;
- this prefix is a palindrome of length at least two.

A bracket sequence is called regular if it is possible to obtain a correct arithmetic expression by inserting characters '+' and '1' into this sequence. For example, sequences (())(), () and (()(())) are regular, while )(, (() and (()))( are not.

The bracket sequence is called palindrome if it reads the same back and forth. For example, the bracket sequences )), (( and )(() are palindromes, while bracket sequences (), )( and ))( are not palindromes.

You stop performing the operations when it's not possible to find a good prefix. Your task is to find the number of operations you will perform on the given string and the number of remaining characters in the string.

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

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

The first line of the test case contains one integer $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$) — the length of the bracket sequence.

The second line of the test case contains $$$n$$$ characters '(' and/or ')' — the bracket sequence itself.

It is guaranteed that the sum of $$$n$$$ over all test cases do not exceed $$$5 \cdot 10^5$$$ ($$$\sum n \le 5 \cdot 10^5$$$).

## Output Format
For each test case, print two integers $$$c$$$ and $$$r$$$ — the number of operations you will perform on the given bracket sequence and the number of characters that remain in the string after performing all operations.

## Examples
```input
5
2
()
3
())
4
((((
5
)((()
6
)((()(
```
```output
1 0
1 1
2 0
1 0
1 1
```

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

# Problem
In this problem, we will consider complete undirected graphs consisting of $$$n$$$ vertices with weighted edges. The weight of each edge is an integer from $$$1$$$ to $$$k$$$.

An undirected graph is considered beautiful if the sum of weights of all edges incident to vertex $$$1$$$ is equal to the weight of MST in the graph. MST is the minimum spanning tree — a tree consisting of $$$n-1$$$ edges of the graph, which connects all $$$n$$$ vertices and has the minimum sum of weights among all such trees; the weight of MST is the sum of weights of all edges in it.

Calculate the number of complete beautiful graphs having exactly $$$n$$$ vertices and the weights of edges from $$$1$$$ to $$$k$$$. Since the answer might be large, print it modulo $$$998244353$$$.

## Input Format
The only line contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 250$$$; $$$1 \le k \le 250$$$).

## Output Format
Print one integer — the number of complete beautiful graphs having exactly $$$n$$$ vertices and the weights of edges from $$$1$$$ to $$$k$$$. Since the answer might be large, print it modulo $$$998244353$$$.

## Examples
```input
3 2
```
```output
5
```
-----
```input
4 4
```
```output
571
```
-----
```input
6 9
```
```output
310640163
```
-----
```input
42 13
```
```output
136246935
```

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
Some country is populated by wizards. They want to organize a demonstration.

There are n people living in the city, x of them are the wizards who will surely go to the demonstration. Other city people (n - x people) do not support the wizards and aren't going to go to the demonstration. We know that the city administration will react only to the demonstration involving at least y percent of the city people. Having considered the matter, the wizards decided to create clone puppets which can substitute the city people on the demonstration.

So all in all, the demonstration will involve only the wizards and their puppets. The city administration cannot tell the difference between a puppet and a person, so, as they calculate the percentage, the administration will consider the city to be consisting of only n people and not containing any clone puppets.

Help the wizards and find the minimum number of clones to create to that the demonstration had no less than y percent of the city people.

## Input Format
The first line contains three space-separated integers, n, x, y (1 ≤ n, x, y ≤ 104, x ≤ n) — the number of citizens in the city, the number of wizards and the percentage the administration needs, correspondingly.

Please note that y can exceed 100 percent, that is, the administration wants to see on a demonstration more people that actually live in the city ( > n).

## Output Format
Print a single integer — the answer to the problem, the minimum number of clones to create, so that the demonstration involved no less than y percent of n (the real total city population).

## Examples
```input
10 1 14
```
```output
1
```
-----
```input
20 10 50
```
```output
0
```
-----
```input
1000 352 146
```
```output
1108
```

## Note
In the first sample it is necessary that at least 14% of 10 people came to the demonstration. As the number of people should be integer, then at least two people should come. There is only one wizard living in the city and he is going to come. That isn't enough, so he needs to create one clone.

In the second sample 10 people should come to the demonstration. The city has 10 wizards. They will all come to the demonstration, so nobody has to create any clones.

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 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 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
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 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: 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 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
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 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
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.
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
Polycarp has a poor memory. Each day he can remember no more than $$$3$$$ of different letters.

Polycarp wants to write a non-empty string of $$$s$$$ consisting of lowercase Latin letters, taking minimum number of days. In how many days will he be able to do it?

Polycarp initially has an empty string and can only add characters to the end of that string.

For example, if Polycarp wants to write the string lollipops, he will do it in $$$2$$$ days:

- on the first day Polycarp will memorize the letters l, o, i and write lolli;
- On the second day Polycarp will remember the letters p, o, s, add pops to the resulting line and get the line lollipops.

If Polycarp wants to write the string stringology, he will do it in $$$4$$$ days:

- in the first day will be written part str;
- on day two will be written part ing;
- on the third day, part of olog will be written;
- on the fourth day, part of y will be written.

For a given string $$$s$$$, print the minimum number of days it will take Polycarp to write it.

## 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 consists of a non-empty string $$$s$$$ consisting of lowercase Latin letters (the length of the string $$$s$$$ does not exceed $$$2 \cdot 10^5$$$) — the string Polycarp wants to construct.

It is guaranteed that the sum of string lengths $$$s$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

## Output Format
For each test case, print a single number — minimum number of days it will take Polycarp to write the string $$$s$$$ from memory.

## Examples
```input
6
lollipops
stringology
abracadabra
codeforces
test
f
```
```output
2
4
3
4
1
1
```

Now solve the problem and return the code.