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 range of positive integers from $$$l$$$ to $$$r$$$.

Find such a pair of integers $$$(x, y)$$$ that $$$l \le x, y \le r$$$, $$$x \ne y$$$ and $$$x$$$ divides $$$y$$$.

If there are multiple answers, print any of them.

You are also asked to answer $$$T$$$ independent queries.

## Input Format
The first line contains a single integer $$$T$$$ ($$$1 \le T \le 1000$$$) — the number of queries.

Each of the next $$$T$$$ lines contains two integers $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le 998244353$$$) — inclusive borders of the range.

It is guaranteed that testset only includes queries, which have at least one suitable pair.

## Output Format
Print $$$T$$$ lines, each line should contain the answer — two integers $$$x$$$ and $$$y$$$ such that $$$l \le x, y \le r$$$, $$$x \ne y$$$ and $$$x$$$ divides $$$y$$$. The answer in the $$$i$$$-th line should correspond to the $$$i$$$-th query from the input.

If there are multiple answers, print any of them.

## Examples
```input
3
1 10
3 14
1 10
```
```output
1 7
3 9
5 10
```

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 string $$$s$$$ of length $$$n$$$ consisting only of lowercase Latin letters.

A substring of a string is a contiguous subsequence of that string. So, string "forces" is substring of string "codeforces", but string "coder" is not.

Your task is to calculate the number of ways to remove exactly one substring from this string in such a way that all remaining characters are equal (the number of distinct characters either zero or one).

It is guaranteed that there is at least two different characters in $$$s$$$.

Note that you can remove the whole string and it is correct. Also note that you should remove at least one character.

Since the answer can be rather large (not very large though) print it modulo $$$998244353$$$.

If you are Python programmer, consider using PyPy instead of Python when you submit your code.

## Input Format
The first line of the input contains one integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the length of the string $$$s$$$.

The second line of the input contains the string $$$s$$$ of length $$$n$$$ consisting only of lowercase Latin letters.

It is guaranteed that there is at least two different characters in $$$s$$$.

## Output Format
Print one integer — the number of ways modulo $$$998244353$$$ to remove exactly one substring from $$$s$$$ in such way that all remaining characters are equal.

## Examples
```input
4
abaa
```
```output
6
```
-----
```input
7
aacdeee
```
```output
6
```
-----
```input
2
az
```
```output
3
```

## Note
Let $$$s[l; r]$$$ be the substring of $$$s$$$ from the position $$$l$$$ to the position $$$r$$$ inclusive.

Then in the first example you can remove the following substrings:

- $$$s[1; 2]$$$;
- $$$s[1; 3]$$$;
- $$$s[1; 4]$$$;
- $$$s[2; 2]$$$;
- $$$s[2; 3]$$$;
- $$$s[2; 4]$$$.

In the second example you can remove the following substrings:

- $$$s[1; 4]$$$;
- $$$s[1; 5]$$$;
- $$$s[1; 6]$$$;
- $$$s[1; 7]$$$;
- $$$s[2; 7]$$$;
- $$$s[3; 7]$$$.

In the third example you can remove the following substrings:

- $$$s[1; 1]$$$;
- $$$s[1; 2]$$$;
- $$$s[2; 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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given an angle $$$\text{ang}$$$.

The Jury asks You to find such regular $$$n$$$-gon (regular polygon with $$$n$$$ vertices) that it has three vertices $$$a$$$, $$$b$$$ and $$$c$$$ (they can be non-consecutive) with $$$\angle{abc} = \text{ang}$$$ or report that there is no such $$$n$$$-gon.

If there are several answers, print the minimal one. It is guarantied that if answer exists then it doesn't exceed $$$998244353$$$.

## Input Format
The first line contains single integer $$$T$$$ ($$$1 \le T \le 180$$$) — the number of queries.

Each of the next $$$T$$$ lines contains one integer $$$\text{ang}$$$ ($$$1 \le \text{ang} < 180$$$) — the angle measured in degrees.

## Output Format
For each query print single integer $$$n$$$ ($$$3 \le n \le 998244353$$$) — minimal possible number of vertices in the regular $$$n$$$-gon or $$$-1$$$ if there is no such $$$n$$$.

## Examples
```input
4
54
50
2
178
```
```output
10
18
90
180
```

## Note
The answer for the first query is on the picture above.

The answer for the second query is reached on a regular $$$18$$$-gon. For example, $$$\angle{v_2 v_1 v_6} = 50^{\circ}$$$.

The example angle for the third query is $$$\angle{v_{11} v_{10} v_{12}} = 2^{\circ}$$$.

In the fourth query, minimal possible $$$n$$$ is $$$180$$$ (not $$$90$$$).

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
Vasya is preparing a contest, and now he has written a statement for an easy problem. The statement is a string of length $$$n$$$ consisting of lowercase Latin latters. Vasya thinks that the statement can be considered hard if it contains a subsequence hard; otherwise the statement is easy. For example, hard, hzazrzd, haaaaard can be considered hard statements, while har, hart and drah are easy statements.

Vasya doesn't want the statement to be hard. He may remove some characters from the statement in order to make it easy. But, of course, some parts of the statement can be crucial to understanding. Initially the ambiguity of the statement is $$$0$$$, and removing $$$i$$$-th character increases the ambiguity by $$$a_i$$$ (the index of each character is considered as it was in the original statement, so, for example, if you delete character r from hard, and then character d, the index of d is still $$$4$$$ even though you delete it from the string had).

Vasya wants to calculate the minimum ambiguity of the statement, if he removes some characters (possibly zero) so that the statement is easy. Help him to do it!

Recall that subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements.

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

The second line contains one string $$$s$$$ of length $$$n$$$, consisting of lowercase Latin letters — the statement written by Vasya.

The third line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 998244353$$$).

## Output Format
Print minimum possible ambiguity of the statement after Vasya deletes some (possibly zero) characters so the resulting statement is easy.

## Examples
```input
6
hhardh
3 2 9 11 7 1
```
```output
5
```
-----
```input
8
hhzarwde
3 2 6 9 4 8 7 1
```
```output
4
```
-----
```input
6
hhaarr
1 2 3 4 5 6
```
```output
0
```

## Note
In the first example, first two characters are removed so the result is ardh.

In the second example, $$$5$$$-th character is removed so the result is hhzawde.

In the third example there's no need to remove anything.

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
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 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: 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 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
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 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: 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 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 $$$s$$$ consisting of $$$n$$$ digits from $$$1$$$ to $$$9$$$.

You have to divide it into at least two segments (segment — is a consecutive sequence of elements) (in other words, you have to place separators between some digits of the sequence) in such a way that each element belongs to exactly one segment and if the resulting division will be represented as an integer numbers sequence then each next element of this sequence will be strictly greater than the previous one.

More formally: if the resulting division of the sequence is $$$t_1, t_2, \dots, t_k$$$, where $$$k$$$ is the number of element in a division, then for each $$$i$$$ from $$$1$$$ to $$$k-1$$$ the condition $$$t_{i} < t_{i + 1}$$$ (using numerical comparing, it means that the integer representations of strings are compared) should be satisfied.

For example, if $$$s=654$$$ then you can divide it into parts $$$[6, 54]$$$ and it will be suitable division. But if you will divide it into parts $$$[65, 4]$$$ then it will be bad division because $$$65 > 4$$$. If $$$s=123$$$ then you can divide it into parts $$$[1, 23]$$$, $$$[1, 2, 3]$$$ but not into parts $$$[12, 3]$$$.

Your task is to find any suitable division for each of the $$$q$$$ independent queries.

## Input Format
The first line of the input contains one integer $$$q$$$ ($$$1 \le q \le 300$$$) — the number of queries.

The first line of the $$$i$$$-th query contains one integer number $$$n_i$$$ ($$$2 \le n_i \le 300$$$) — the number of digits in the $$$i$$$-th query.

The second line of the $$$i$$$-th query contains one string $$$s_i$$$ of length $$$n_i$$$ consisting only of digits from $$$1$$$ to $$$9$$$.

## Output Format
If the sequence of digits in the $$$i$$$-th query cannot be divided into at least two parts in a way described in the problem statement, print the single line "NO" for this query.

Otherwise in the first line of the answer to this query print "YES", on the second line print $$$k_i$$$ — the number of parts in your division of the $$$i$$$-th query sequence and in the third line print $$$k_i$$$ strings $$$t_{i, 1}, t_{i, 2}, \dots, t_{i, k_i}$$$ — your division. Parts should be printed in order of the initial string digits. It means that if you write the parts one after another without changing their order then you'll get the string $$$s_i$$$.

See examples for better understanding.

## Examples
```input
4
6
654321
4
1337
2
33
4
2122
```
```output
YES
3
6 54 321
YES
3
1 3 37
NO
YES
2
21 22
```

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
Today at the lesson of mathematics, Petya learns about the digital root.

The digital root of a non-negative integer is the single digit value obtained by an iterative process of summing digits, on each iteration using the result from the previous iteration to compute a digit sum. The process continues until a single-digit number is reached.

Let's denote the digital root of $$$x$$$ as $$$S(x)$$$. Then $$$S(5)=5$$$, $$$S(38)=S(3+8=11)=S(1+1=2)=2$$$, $$$S(10)=S(1+0=1)=1$$$.

As a homework Petya got $$$n$$$ tasks of the form: find $$$k$$$-th positive number whose digital root is $$$x$$$.

Petya has already solved all the problems, but he doesn't know if it's right. Your task is to solve all $$$n$$$ tasks from Petya's homework.

## Input Format
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 10^3$$$) — the number of tasks in Petya's homework. The next $$$n$$$ lines contain two integers $$$k_i$$$ ($$$1 \le k_i \le 10^{12}$$$) and $$$x_i$$$ ($$$1 \le x_i \le 9$$$) — $$$i$$$-th Petya's task in which you need to find a $$$k_i$$$-th positive number, the digital root of which is $$$x_i$$$.

## Output Format
Output $$$n$$$ lines, $$$i$$$-th line should contain a single integer — the answer to the $$$i$$$-th problem.

## Examples
```input
3
1 5
5 2
3 1
```
```output
5
38
19
```

Now solve the problem and return the code.