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
A permutation of size $$$n$$$ is an array of size $$$n$$$ such that each integer from $$$1$$$ to $$$n$$$ occurs exactly once in this array. An inversion in a permutation $$$p$$$ is a pair of indices $$$(i, j)$$$ such that $$$i > j$$$ and $$$a_i < a_j$$$. For example, a permutation $$$[4, 1, 3, 2]$$$ contains $$$4$$$ inversions: $$$(2, 1)$$$, $$$(3, 1)$$$, $$$(4, 1)$$$, $$$(4, 3)$$$.

You are given a permutation $$$p$$$ of size $$$n$$$. However, the numbers on some positions are replaced by $$$-1$$$. Let the valid permutation be such a replacement of $$$-1$$$ in this sequence back to numbers from $$$1$$$ to $$$n$$$ in such a way that the resulting sequence is a permutation of size $$$n$$$.

The given sequence was turned into a valid permutation randomly with the equal probability of getting each valid permutation.

Calculate the expected total number of inversions in the resulting valid permutation.

It can be shown that it is in the form of $$$\frac{P}{Q}$$$ where $$$P$$$ and $$$Q$$$ are non-negative integers and $$$Q \ne 0$$$. Report the value of $$$P \cdot Q^{-1} \pmod {998244353}$$$.

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

The second line contains $$$n$$$ integers $$$p_1, p_2, \dots, p_n$$$ ($$$-1 \le p_i \le n$$$, $$$p_i \ne 0$$$) — the initial sequence.

It is guaranteed that all elements not equal to $$$-1$$$ are pairwise distinct.

## Output Format
Print a single integer — the expected total number of inversions in the resulting valid permutation.

It can be shown that it is in the form of $$$\frac{P}{Q}$$$ where $$$P$$$ and $$$Q$$$ are non-negative integers and $$$Q \ne 0$$$. Report the value of $$$P \cdot Q^{-1} \pmod {998244353}$$$.

## Examples
```input
3
3 -1 -1
```
```output
499122179
```
-----
```input
2
1 2
```
```output
0
```
-----
```input
2
-1 -1
```
```output
499122177
```

## Note
In the first example two resulting valid permutations are possible:

- $$$[3, 1, 2]$$$ — $$$2$$$ inversions;
- $$$[3, 2, 1]$$$ — $$$3$$$ inversions.

The expected value is $$$\frac{2 \cdot 1 + 3 \cdot 1}{2} = 2.5$$$.

In the second example no $$$-1$$$ are present, thus the only valid permutation is possible — the given one. It has $$$0$$$ inversions.

In the third example there are two resulting valid permutations — one with $$$0$$$ inversions and one with $$$1$$$ inversion.

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

# Problem
All bus tickets in Berland have their numbers. A number consists of $$$n$$$ digits ($$$n$$$ is even). Only $$$k$$$ decimal digits $$$d_1, d_2, \dots, d_k$$$ can be used to form ticket numbers. If $$$0$$$ is among these digits, then numbers may have leading zeroes. For example, if $$$n = 4$$$ and only digits $$$0$$$ and $$$4$$$ can be used, then $$$0000$$$, $$$4004$$$, $$$4440$$$ are valid ticket numbers, and $$$0002$$$, $$$00$$$, $$$44443$$$ are not.

A ticket is lucky if the sum of first $$$n / 2$$$ digits is equal to the sum of remaining $$$n / 2$$$ digits.

Calculate the number of different lucky tickets in Berland. Since the answer may be big, print it modulo $$$998244353$$$.

## Input Format
The first line contains two integers $$$n$$$ and $$$k$$$ $$$(2 \le n \le 2 \cdot 10^5, 1 \le k \le 10)$$$ — the number of digits in each ticket number, and the number of different decimal digits that may be used. $$$n$$$ is even.

The second line contains a sequence of pairwise distinct integers $$$d_1, d_2, \dots, d_k$$$ $$$(0 \le d_i \le 9)$$$ — the digits that may be used in ticket numbers. The digits are given in arbitrary order.

## Output Format
Print the number of lucky ticket numbers, taken modulo $$$998244353$$$.

## Examples
```input
4 2
1 8
```
```output
6
```
-----
```input
20 1
6
```
```output
1
```
-----
```input
10 5
6 1 4 0 3
```
```output
569725
```
-----
```input
1000 7
5 4 0 1 8 3 2
```
```output
460571165
```

## Note
In the first example there are $$$6$$$ lucky ticket numbers: $$$1111$$$, $$$1818$$$, $$$1881$$$, $$$8118$$$, $$$8181$$$ and $$$8888$$$.

There is only one ticket number in the second example, it consists of $$$20$$$ digits $$$6$$$. This ticket number is lucky, so the answer is $$$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: 3.0 seconds
Memory limit: 512.0 MB

# Problem
Cardbluff is popular sport game in Telegram. Each Cardbluff player has ever dreamed about entrance in the professional layer. There are $$$n$$$ judges now in the layer and you are trying to pass the entrance exam. You have a number $$$k$$$ — your skill in Cardbluff.

Each judge has a number $$$a_i$$$ — an indicator of uncertainty about your entrance to the professional layer and a number $$$e_i$$$ — an experience playing Cardbluff. To pass the exam you need to convince all judges by playing with them. You can play only one game with each judge. As a result of a particular game, you can divide the uncertainty of $$$i$$$-th judge by any natural divisor of $$$a_i$$$ which is at most $$$k$$$. If GCD of all indicators is equal to $$$1$$$, you will enter to the professional layer and become a judge.

Also, you want to minimize the total amount of spent time. So, if you play with $$$x$$$ judges with total experience $$$y$$$ you will spend $$$x \cdot y$$$ seconds.

Print minimal time to enter to the professional layer or $$$-1$$$ if it's impossible.

## Input Format
There are two numbers in the first line $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 10^6$$$, $$$1 \leq k \leq 10^{12}$$$) — the number of judges and your skill in Cardbluff.

The second line contains $$$n$$$ integers, where $$$i$$$-th number $$$a_i$$$ ($$$1 \leq a_i \leq 10^{12}$$$) — the uncertainty of $$$i$$$-th judge

The third line contains $$$n$$$ integers in the same format ($$$1 \leq e_i \leq 10^9$$$), $$$e_i$$$ — the experience of $$$i$$$-th judge.

## Output Format
Print the single integer — minimal number of seconds to pass exam, or $$$-1$$$ if it's impossible

## Examples
```input
3 6
30 30 30
100 4 5
```
```output
18
```
-----
```input
1 1000000
1
100
```
```output
0
```
-----
```input
3 5
7 7 7
1 1 1
```
```output
-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: 4.0 seconds
Memory limit: 256.0 MB

# Problem
Let's define radix sum of number $$$a$$$ consisting of digits $$$a_1, \ldots ,a_k$$$ and number $$$b$$$ consisting of digits $$$b_1, \ldots ,b_k$$$(we add leading zeroes to the shorter number to match longer length) as number $$$s(a,b)$$$ consisting of digits $$$(a_1+b_1)\mod 10, \ldots ,(a_k+b_k)\mod 10$$$. The radix sum of several integers is defined as follows: $$$s(t_1, \ldots ,t_n)=s(t_1,s(t_2, \ldots ,t_n))$$$

You are given an array $$$x_1, \ldots ,x_n$$$. The task is to compute for each integer $$$i (0 \le i < n)$$$ number of ways to consequently choose one of the integers from the array $$$n$$$ times, so that the radix sum of these integers is equal to $$$i$$$. Calculate these values modulo $$$2^{58}$$$.

## Input Format
The first line contains integer $$$n$$$ — the length of the array($$$1 \leq n \leq 100000$$$).

The second line contains $$$n$$$ integers $$$x_1, \ldots x_n$$$ — array elements($$$0 \leq x_i < 100000$$$).

## Output Format
Output $$$n$$$ integers $$$y_0, \ldots, y_{n-1}$$$ — $$$y_i$$$ should be equal to corresponding number of ways modulo $$$2^{58}$$$.

## Examples
```input
2
5 6
```
```output
1
2
```
-----
```input
4
5 7 5 7
```
```output
16
0
64
0
```

## Note
In the first example there exist sequences: sequence $$$(5,5)$$$ with radix sum $$$0$$$, sequence $$$(5,6)$$$ with radix sum $$$1$$$, sequence $$$(6,5)$$$ with radix sum $$$1$$$, sequence $$$(6,6)$$$ with radix sum $$$2$$$.

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

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

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

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
A string is called bracket sequence if it does not contain any characters other than "(" and ")". A bracket sequence is called regular if it it is possible to obtain correct arithmetic expression by inserting characters "+" and "1" into this sequence. For example, "", "(())" and "()()" are regular bracket sequences; "))" and ")((" are bracket sequences (but not regular ones), and "(a)" and "(1)+(1)" are not bracket sequences at all.

You have a number of strings; each string is a bracket sequence of length $$$2$$$. So, overall you have $$$cnt_1$$$ strings "((", $$$cnt_2$$$ strings "()", $$$cnt_3$$$ strings ")(" and $$$cnt_4$$$ strings "))". You want to write all these strings in some order, one after another; after that, you will get a long bracket sequence of length $$$2(cnt_1 + cnt_2 + cnt_3 + cnt_4)$$$. You wonder: is it possible to choose some order of the strings you have such that you will get a regular bracket sequence? Note that you may not remove any characters or strings, and you may not add anything either.

## Input Format
The input consists of four lines, $$$i$$$-th of them contains one integer $$$cnt_i$$$ ($$$0 \le cnt_i \le 10^9$$$).

## Output Format
Print one integer: $$$1$$$ if it is possible to form a regular bracket sequence by choosing the correct order of the given strings, $$$0$$$ otherwise.

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

## Note
In the first example it is possible to construct a string "(())()(()((()()()())))", which is a regular bracket sequence.

In the second example it is possible to construct a string "", which is a regular bracket 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 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.5 seconds
Memory limit: 256.0 MB

# Problem
You came to a local shop and want to buy some chocolate bars. There are $$$n$$$ bars in the shop, $$$i$$$-th of them costs $$$a_i$$$ coins (and you want to buy all of them).

You have $$$m$$$ different coupons that allow you to buy chocolate bars. $$$i$$$-th coupon allows you to buy $$$q_i$$$ chocolate bars while you have to pay only for the $$$q_i - 1$$$ most expensive ones (so, the cheapest bar of those $$$q_i$$$ bars is for free).

You can use only one coupon; if you use coupon $$$i$$$, you have to choose $$$q_i$$$ bars and buy them using the coupon, and buy all the remaining $$$n - q_i$$$ bars without any discounts.

To decide which coupon to choose, you want to know what will be the minimum total amount of money you have to pay if you use one of the coupons optimally.

## Input Format
The first line contains one integer $$$n$$$ ($$$2 \le n \le 3 \cdot 10^5$$$) — the number of chocolate bars in the shop.

The second line contains $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$1 \le a_i \le 10^9$$$), where $$$a_i$$$ is the cost of $$$i$$$-th chocolate bar.

The third line contains one integer $$$m$$$ ($$$1 \le m \le n - 1$$$) — the number of coupons you have.

The fourth line contains $$$m$$$ integers $$$q_1$$$, $$$q_2$$$, ..., $$$q_m$$$ ($$$2 \le q_i \le n$$$), where $$$q_i$$$ is the number of chocolate bars you have to buy using $$$i$$$-th coupon so that the least expensive of them will be for free. All values of $$$q_i$$$ are pairwise distinct.

## Output Format
Print $$$m$$$ integers, $$$i$$$-th of them should be the minimum amount of money you have to pay if you buy $$$q_i$$$ bars with $$$i$$$-th coupon, and all the remaining bars one by one for their full price.

## Examples
```input
7
7 1 3 1 4 10 8
2
3 4
```
```output
27
30
```

## Note
Consider the first example.

If we use the first coupon, we may choose chocolate bars having indices $$$1$$$, $$$6$$$ and $$$7$$$, and we pay $$$18$$$ coins for them and $$$9$$$ coins for all other bars.

If we use the second coupon, we may choose chocolate bars having indices $$$1$$$, $$$5$$$, $$$6$$$ and $$$7$$$, and we pay $$$25$$$ coins for them and $$$5$$$ coins for all other bars.

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 have a long fence which consists of $$$n$$$ sections. Unfortunately, it is not painted, so you decided to hire $$$q$$$ painters to paint it. $$$i$$$-th painter will paint all sections $$$x$$$ such that $$$l_i \le x \le r_i$$$.

Unfortunately, you are on a tight budget, so you may hire only $$$q - 2$$$ painters. Obviously, only painters you hire will do their work.

You want to maximize the number of painted sections if you choose $$$q - 2$$$ painters optimally. A section is considered painted if at least one painter paints it.

## Input Format
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$3 \le n, q \le 5000$$$) — the number of sections and the number of painters availible for hire, respectively.

Then $$$q$$$ lines follow, each describing one of the painters: $$$i$$$-th line contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$).

## Output Format
Print one integer — maximum number of painted sections if you hire $$$q - 2$$$ painters.

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

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

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

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

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You have a set of items, each having some integer weight not greater than $$$8$$$. You denote that a subset of items is good if total weight of items in the subset does not exceed $$$W$$$.

You want to calculate the maximum possible weight of a good subset of items. Note that you have to consider the empty set and the original set when calculating the answer.

## Input Format
The first line contains one integer $$$W$$$ ($$$0 \le W \le 10^{18}$$$) — the maximum total weight of a good subset.

The second line denotes the set of items you have. It contains $$$8$$$ integers $$$cnt_1$$$, $$$cnt_2$$$, ..., $$$cnt_8$$$ ($$$0 \le cnt_i \le 10^{16}$$$), where $$$cnt_i$$$ is the number of items having weight $$$i$$$ in the set.

## Output Format
Print one integer — the maximum possible weight of a good subset of items.

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

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

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

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

Execution time limit: 3.0 seconds
Memory limit: 256.0 MB

# Problem
You are given a string $$$s$$$ of length $$$n$$$ consisting of lowercase Latin letters. You may apply some operations to this string: in one operation you can delete some contiguous substring of this string, if all letters in the substring you delete are equal. For example, after deleting substring bbbb from string abbbbaccdd we get the string aaccdd.

Calculate the minimum number of operations to delete the whole string $$$s$$$.

## Input Format
The first line contains one integer $$$n$$$ ($$$1 \le n \le 500$$$) — the length of string $$$s$$$.

The second line contains the string $$$s$$$ ($$$|s| = n$$$) consisting of lowercase Latin letters.

## Output Format
Output a single integer — the minimal number of operation to delete string $$$s$$$.

## Examples
```input
5
abaca
```
```output
3
```
-----
```input
8
abcddcba
```
```output
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
For some array $$$c$$$, let's denote a greedy subsequence as a sequence of indices $$$p_1$$$, $$$p_2$$$, ..., $$$p_l$$$ such that $$$1 \le p_1 < p_2 < \dots < p_l \le |c|$$$, and for each $$$i \in [1, l - 1]$$$, $$$p_{i + 1}$$$ is the minimum number such that $$$p_{i + 1} > p_i$$$ and $$$c[p_{i + 1}] > c[p_i]$$$.

You are given an array $$$a_1, a_2, \dots, a_n$$$. For each its subsegment of length $$$k$$$, calculate the length of its longest greedy subsequence.

## Input Format
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 10^6$$$) — the length of array $$$a$$$ and the length of subsegments.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$) — array $$$a$$$.

## Output Format
Print $$$n - k + 1$$$ integers — the maximum lengths of greedy subsequences of each subsegment having length $$$k$$$. The first number should correspond to subsegment $$$a[1..k]$$$, the second — to subsegment $$$a[2..k + 1]$$$, and so on.

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

## Note
In the first example:

- $$$[1, 5, 2, 5]$$$ — the longest greedy subsequences are $$$1, 2$$$ ($$$[c_1, c_2] = [1, 5]$$$) or $$$3, 4$$$ ($$$[c_3, c_4] = [2, 5]$$$).
- $$$[5, 2, 5, 3]$$$ — the sequence is $$$2, 3$$$ ($$$[c_2, c_3] = [2, 5]$$$).
- $$$[2, 5, 3, 6]$$$ — the sequence is $$$1, 2, 4$$$ ($$$[c_1, c_2, c_4] = [2, 5, 6]$$$).

In the second example:

- $$$[4, 5, 2, 5, 3, 6]$$$ — the longest greedy subsequences are $$$1, 2, 6$$$ ($$$[c_1, c_2, c_6] = [4, 5, 6]$$$) or $$$3, 4, 6$$$ ($$$[c_3, c_4, c_6] = [2, 5, 6]$$$).
- $$$[5, 2, 5, 3, 6, 6]$$$ — the subsequence is $$$2, 3, 5$$$ ($$$[c_2, c_3, c_5] = [2, 5, 6]$$$).

Now solve the problem and return the code.