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
Consider some set of distinct characters $$$A$$$ and some string $$$S$$$, consisting of exactly $$$n$$$ characters, where each character is present in $$$A$$$.

You are given an array of $$$m$$$ integers $$$b$$$ ($$$b_1 < b_2 < \dots < b_m$$$).

You are allowed to perform the following move on the string $$$S$$$:

1. Choose some valid $$$i$$$ and set $$$k = b_i$$$;
2. Take the first $$$k$$$ characters of $$$S = Pr_k$$$;
3. Take the last $$$k$$$ characters of $$$S = Su_k$$$;
4. Substitute the first $$$k$$$ characters of $$$S$$$ with the reversed $$$Su_k$$$;
5. Substitute the last $$$k$$$ characters of $$$S$$$ with the reversed $$$Pr_k$$$.

For example, let's take a look at $$$S =$$$ "abcdefghi" and $$$k = 2$$$. $$$Pr_2 =$$$ "ab", $$$Su_2 =$$$ "hi". Reversed $$$Pr_2 =$$$ "ba", $$$Su_2 =$$$ "ih". Thus, the resulting $$$S$$$ is "ihcdefgba".

The move can be performed arbitrary number of times (possibly zero). Any $$$i$$$ can be selected multiple times over these moves.

Let's call some strings $$$S$$$ and $$$T$$$ equal if and only if there exists such a sequence of moves to transmute string $$$S$$$ to string $$$T$$$. For the above example strings "abcdefghi" and "ihcdefgba" are equal. Also note that this implies $$$S = S$$$.

The task is simple. Count the number of distinct strings.

The answer can be huge enough, so calculate it modulo $$$998244353$$$.

## Input Format
The first line contains three integers $$$n$$$, $$$m$$$ and $$$|A|$$$ ($$$2 \le n \le 10^9$$$, $$$1 \le m \le min(\frac n 2, 2 \cdot 10^5)$$$, $$$1 \le |A| \le 10^9$$$) — the length of the strings, the size of the array $$$b$$$ and the size of the set $$$A$$$, respectively.

The second line contains $$$m$$$ integers $$$b_1, b_2, \dots, b_m$$$ ($$$1 \le b_i \le \frac n 2$$$, $$$b_1 < b_2 < \dots < b_m$$$).

## Output Format
Print a single integer — the number of distinct strings of length $$$n$$$ with characters from set $$$A$$$ modulo $$$998244353$$$.

## Examples
```input
3 1 2
1
```
```output
6
```
-----
```input
9 2 26
2 3
```
```output
150352234
```
-----
```input
12 3 1
2 5 6
```
```output
1
```

## Note
Here are all the distinct strings for the first example. The chosen letters 'a' and 'b' are there just to show that the characters in $$$A$$$ are different.

1. "aaa"
2. "aab" = "baa"
3. "aba"
4. "abb" = "bba"
5. "bab"
6. "bbb"

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 tree with $$$n$$$ vertices; its root is vertex $$$1$$$. Also there is a token, initially placed in the root. You can move the token to other vertices. Let's assume current vertex of token is $$$v$$$, then you make any of the following two possible moves:

- move down to any leaf in subtree of $$$v$$$;
- if vertex $$$v$$$ is a leaf, then move up to the parent no more than $$$k$$$ times. In other words, if $$$h(v)$$$ is the depth of vertex $$$v$$$ (the depth of the root is $$$0$$$), then you can move to vertex $$$to$$$ such that $$$to$$$ is an ancestor of $$$v$$$ and $$$h(v) - k \le h(to)$$$.

Consider that root is not a leaf (even if its degree is $$$1$$$). Calculate the maximum number of different leaves you can visit during one sequence of moves.

## Input Format
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k < n \le 10^6$$$) — the number of vertices in the tree and the restriction on moving up, respectively.

The second line contains $$$n - 1$$$ integers $$$p_2, p_3, \dots, p_n$$$, where $$$p_i$$$ is the parent of vertex $$$i$$$.

It is guaranteed that the input represents a valid tree, rooted at $$$1$$$.

## Output Format
Print one integer — the maximum possible number of different leaves you can visit.

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

## Note
The graph from the first example:

One of the optimal ways is the next one: $$$1 \rightarrow 2 \rightarrow 1 \rightarrow 5 \rightarrow 3 \rightarrow 7 \rightarrow 4 \rightarrow 6$$$.

The graph from the second example:

One of the optimal ways is the next one: $$$1 \rightarrow 7 \rightarrow 5 \rightarrow 8$$$. Note that there is no way to move from $$$6$$$ to $$$7$$$ or $$$8$$$ and vice versa.

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
Let's denote (yet again) the sequence of Fibonacci strings:

$$$F(0) = $$$ 0, $$$F(1) = $$$ 1, $$$F(i) = F(i - 2) + F(i - 1)$$$, where the plus sign denotes the concatenation of two strings.

Let's denote the lexicographically sorted sequence of suffixes of string $$$F(i)$$$ as $$$A(F(i))$$$. For example, $$$F(4)$$$ is 01101, and $$$A(F(4))$$$ is the following sequence: 01, 01101, 1, 101, 1101. Elements in this sequence are numbered from $$$1$$$.

Your task is to print $$$m$$$ first characters of $$$k$$$-th element of $$$A(F(n))$$$. If there are less than $$$m$$$ characters in this suffix, then output the whole suffix.

## Input Format
The only line of the input contains three numbers $$$n$$$, $$$k$$$ and $$$m$$$ ($$$1 \le n, m \le 200$$$, $$$1 \le k \le 10^{18}$$$) denoting the index of the Fibonacci string you have to consider, the index of the element of $$$A(F(n))$$$ and the number of characters you have to output, respectively.

It is guaranteed that $$$k$$$ does not exceed the length of $$$F(n)$$$.

## Output Format
Output $$$m$$$ first characters of $$$k$$$-th element of $$$A(F(n))$$$, or the whole element if its length is less than $$$m$$$.

## Examples
```input
4 5 3
```
```output
110
```
-----
```input
4 3 3
```
```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: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You are given a string $$$s$$$, consisting of $$$n$$$ lowercase Latin letters.

A substring of string $$$s$$$ is a continuous segment of letters from $$$s$$$. For example, "defor" is a substring of "codeforces" and "fors" is not.

The length of the substring is the number of letters in it.

Let's call some string of length $$$n$$$ diverse if and only if there is no letter to appear strictly more than $$$\frac n 2$$$ times. For example, strings "abc" and "iltlml" are diverse and strings "aab" and "zz" are not.

Your task is to find any diverse substring of string $$$s$$$ or report that there is none. Note that it is not required to maximize or minimize the length of the resulting substring.

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

The second line is the string $$$s$$$, consisting of exactly $$$n$$$ lowercase Latin letters.

## Output Format
Print "NO" if there is no diverse substring in the string $$$s$$$.

Otherwise the first line should contain "YES". The second line should contain any diverse substring of string $$$s$$$.

## Examples
```input
10
codeforces
```
```output
YES
code
```
-----
```input
5
aaaaa
```
```output
NO
```

## Note
The first example has lots of correct answers.

Please, restrain yourself from asking if some specific answer is correct for some specific test or not, these questions always lead to "No comments" answer.

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
Vasya has got $$$n$$$ books, numbered from $$$1$$$ to $$$n$$$, arranged in a stack. The topmost book has number $$$a_1$$$, the next one — $$$a_2$$$, and so on. The book at the bottom of the stack has number $$$a_n$$$. All numbers are distinct.

Vasya wants to move all the books to his backpack in $$$n$$$ steps. During $$$i$$$-th step he wants to move the book number $$$b_i$$$ into his backpack. If the book with number $$$b_i$$$ is in the stack, he takes this book and all the books above the book $$$b_i$$$, and puts them into the backpack; otherwise he does nothing and begins the next step. For example, if books are arranged in the order $$$[1, 2, 3]$$$ (book $$$1$$$ is the topmost), and Vasya moves the books in the order $$$[2, 1, 3]$$$, then during the first step he will move two books ($$$1$$$ and $$$2$$$), during the second step he will do nothing (since book $$$1$$$ is already in the backpack), and during the third step — one book (the book number $$$3$$$). Note that $$$b_1, b_2, \dots, b_n$$$ are distinct.

Help Vasya! Tell him the number of books he will put into his backpack during each step.

## Input Format
The first line contains one integer $$$n~(1 \le n \le 2 \cdot 10^5)$$$ — the number of books in the stack.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n~(1 \le a_i \le n)$$$ denoting the stack of books.

The third line contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n~(1 \le b_i \le n)$$$ denoting the steps Vasya is going to perform.

All numbers $$$a_1 \dots a_n$$$ are distinct, the same goes for $$$b_1 \dots b_n$$$.

## Output Format
Print $$$n$$$ integers. The $$$i$$$-th of them should be equal to the number of books Vasya moves to his backpack during the $$$i$$$-th step.

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

## Note
The first example is described in the statement.

In the second example, during the first step Vasya will move the books $$$[3, 1, 4]$$$. After that only books $$$2$$$ and $$$5$$$ remain in the stack ($$$2$$$ is above $$$5$$$). During the second step Vasya will take the books $$$2$$$ and $$$5$$$. After that the stack becomes empty, so during next steps Vasya won't move any books.

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
XXI Berland Annual Fair is coming really soon! Traditionally fair consists of $$$n$$$ booths, arranged in a circle. The booths are numbered $$$1$$$ through $$$n$$$ clockwise with $$$n$$$ being adjacent to $$$1$$$. The $$$i$$$-th booths sells some candies for the price of $$$a_i$$$ burles per item. Each booth has an unlimited supply of candies.

Polycarp has decided to spend at most $$$T$$$ burles at the fair. However, he has some plan in mind for his path across the booths:

- at first, he visits booth number $$$1$$$;
- if he has enough burles to buy exactly one candy from the current booth, then he buys it immediately;
- then he proceeds to the next booth in the clockwise order (regardless of if he bought a candy or not).

Polycarp's money is finite, thus the process will end once he can no longer buy candy at any booth.

Calculate the number of candies Polycarp will buy.

## Input Format
The first line contains two integers $$$n$$$ and $$$T$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le T \le 10^{18}$$$) — the number of booths at the fair and the initial amount of burles Polycarp has.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the price of the single candy at booth number $$$i$$$.

## Output Format
Print a single integer — the total number of candies Polycarp will buy.

## Examples
```input
3 38
5 2 5
```
```output
10
```
-----
```input
5 21
2 4 100 2 6
```
```output
6
```

## Note
Let's consider the first example. Here are Polycarp's moves until he runs out of money:

1. Booth $$$1$$$, buys candy for $$$5$$$, $$$T = 33$$$;
2. Booth $$$2$$$, buys candy for $$$2$$$, $$$T = 31$$$;
3. Booth $$$3$$$, buys candy for $$$5$$$, $$$T = 26$$$;
4. Booth $$$1$$$, buys candy for $$$5$$$, $$$T = 21$$$;
5. Booth $$$2$$$, buys candy for $$$2$$$, $$$T = 19$$$;
6. Booth $$$3$$$, buys candy for $$$5$$$, $$$T = 14$$$;
7. Booth $$$1$$$, buys candy for $$$5$$$, $$$T = 9$$$;
8. Booth $$$2$$$, buys candy for $$$2$$$, $$$T = 7$$$;
9. Booth $$$3$$$, buys candy for $$$5$$$, $$$T = 2$$$;
10. Booth $$$1$$$, buys no candy, not enough money;
11. Booth $$$2$$$, buys candy for $$$2$$$, $$$T = 0$$$.

No candy can be bought later. The total number of candies bought is $$$10$$$.

In the second example he has $$$1$$$ burle left at the end of his path, no candy can be bought with this amount.

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

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

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

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
You are given two integers $$$l$$$ and $$$r$$$ ($$$l \le r$$$). Your task is to calculate the sum of numbers from $$$l$$$ to $$$r$$$ (including $$$l$$$ and $$$r$$$) such that each number contains at most $$$k$$$ different digits, and print this sum modulo $$$998244353$$$.

For example, if $$$k = 1$$$ then you have to calculate all numbers from $$$l$$$ to $$$r$$$ such that each number is formed using only one digit. For $$$l = 10, r = 50$$$ the answer is $$$11 + 22 + 33 + 44 = 110$$$.

## Input Format
The only line of the input contains three integers $$$l$$$, $$$r$$$ and $$$k$$$ ($$$1 \le l \le r < 10^{18}, 1 \le k \le 10$$$) — the borders of the segment and the maximum number of different digits.

## Output Format
Print one integer — the sum of numbers from $$$l$$$ to $$$r$$$ such that each number contains at most $$$k$$$ different digits, modulo $$$998244353$$$.

## Examples
```input
10 50 2
```
```output
1230
```
-----
```input
1 2345 10
```
```output
2750685
```
-----
```input
101 154 2
```
```output
2189
```

## Note
For the first example the answer is just the sum of numbers from $$$l$$$ to $$$r$$$ which equals to $$$\frac{50 \cdot 51}{2} - \frac{9 \cdot 10}{2} = 1230$$$. This example also explained in the problem statement but for $$$k = 1$$$.

For the second example the answer is just the sum of numbers from $$$l$$$ to $$$r$$$ which equals to $$$\frac{2345 \cdot 2346}{2} = 2750685$$$.

For the third example the answer is $$$101 + 110 + 111 + 112 + 113 + 114 + 115 + 116 + 117 + 118 + 119 + 121 + 122 + 131 + 133 + 141 + 144 + 151 = 2189$$$.

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
Vova has won $$$n$$$ trophies in different competitions. Each trophy is either golden or silver. The trophies are arranged in a row.

The beauty of the arrangement is the length of the longest subsegment consisting of golden trophies. Vova wants to swap two trophies (not necessarily adjacent ones) to make the arrangement as beautiful as possible — that means, to maximize the length of the longest such subsegment.

Help Vova! Tell him the maximum possible beauty of the arrangement if he is allowed to do at most one swap.

## Input Format
The first line contains one integer $$$n$$$ ($$$2 \le n \le 10^5$$$) — the number of trophies.

The second line contains $$$n$$$ characters, each of them is either G or S. If the $$$i$$$-th character is G, then the $$$i$$$-th trophy is a golden one, otherwise it's a silver trophy.

## Output Format
Print the maximum possible length of a subsegment of golden trophies, if Vova is allowed to do at most one swap.

## Examples
```input
10
GGGSGGGSGG
```
```output
7
```
-----
```input
4
GGGG
```
```output
4
```
-----
```input
3
SSS
```
```output
0
```

## Note
In the first example Vova has to swap trophies with indices $$$4$$$ and $$$10$$$. Thus he will obtain the sequence "GGGGGGGSGS", the length of the longest subsegment of golden trophies is $$$7$$$.

In the second example Vova can make no swaps at all. The length of the longest subsegment of golden trophies in the sequence is $$$4$$$.

In the third example Vova cannot do anything to make the length of the longest subsegment of golden trophies in the sequence greater than $$$0$$$.

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

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

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

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
A multi-subject competition is coming! The competition has $$$m$$$ different subjects participants can choose from. That's why Alex (the coach) should form a competition delegation among his students.

He has $$$n$$$ candidates. For the $$$i$$$-th person he knows subject $$$s_i$$$ the candidate specializes in and $$$r_i$$$ — a skill level in his specialization (this level can be negative!).

The rules of the competition require each delegation to choose some subset of subjects they will participate in. The only restriction is that the number of students from the team participating in each of the chosen subjects should be the same.

Alex decided that each candidate would participate only in the subject he specializes in. Now Alex wonders whom he has to choose to maximize the total sum of skill levels of all delegates, or just skip the competition this year if every valid non-empty delegation has negative sum.

(Of course, Alex doesn't have any spare money so each delegate he chooses must participate in the competition).

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 10^5$$$, $$$1 \le m \le 10^5$$$) — the number of candidates and the number of subjects.

The next $$$n$$$ lines contains two integers per line: $$$s_i$$$ and $$$r_i$$$ ($$$1 \le s_i \le m$$$, $$$-10^4 \le r_i \le 10^4$$$) — the subject of specialization and the skill level of the $$$i$$$-th candidate.

## Output Format
Print the single integer — the maximum total sum of skills of delegates who form a valid delegation (according to rules above) or $$$0$$$ if every valid non-empty delegation has negative sum.

## Examples
```input
6 3
2 6
3 6
2 5
3 5
1 9
3 1
```
```output
22
```
-----
```input
5 3
2 6
3 6
2 5
3 5
1 11
```
```output
23
```
-----
```input
5 2
1 -1
1 -5
2 -1
2 -1
1 -10
```
```output
0
```

## Note
In the first example it's optimal to choose candidates $$$1$$$, $$$2$$$, $$$3$$$, $$$4$$$, so two of them specialize in the $$$2$$$-nd subject and other two in the $$$3$$$-rd. The total sum is $$$6 + 6 + 5 + 5 = 22$$$.

In the second example it's optimal to choose candidates $$$1$$$, $$$2$$$ and $$$5$$$. One person in each subject and the total sum is $$$6 + 6 + 11 = 23$$$.

In the third example it's impossible to obtain a non-negative sum.

Now solve the problem and return the code.