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
Your favorite shop sells $$$n$$$ Kinder Surprise chocolate eggs. You know that exactly $$$s$$$ stickers and exactly $$$t$$$ toys are placed in $$$n$$$ eggs in total.

Each Kinder Surprise can be one of three types:

- it can contain a single sticker and no toy;
- it can contain a single toy and no sticker;
- it can contain both a single sticker and a single toy.

But you don't know which type a particular Kinder Surprise has. All eggs look identical and indistinguishable from each other.

What is the minimum number of Kinder Surprise Eggs you have to buy to be sure that, whichever types they are, you'll obtain at least one sticker and at least one toy?

Note that you do not open the eggs in the purchasing process, that is, you just buy some number of eggs. It's guaranteed that the answer always exists.

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

Next $$$T$$$ lines contain three integers $$$n$$$, $$$s$$$ and $$$t$$$ each ($$$1 \le n \le 10^9$$$, $$$1 \le s, t \le n$$$, $$$s + t \ge n$$$) — the number of eggs, stickers and toys.

All queries are independent.

## Output Format
Print $$$T$$$ integers (one number per query) — the minimum number of Kinder Surprise Eggs you have to buy to be sure that, whichever types they are, you'll obtain at least one sticker and one toy

## Examples
```input
3
10 5 7
10 10 10
2 1 1
```
```output
6
1
2
```

## Note
In the first query, we have to take at least $$$6$$$ eggs because there are $$$5$$$ eggs with only toy inside and, in the worst case, we'll buy all of them.

In the second query, all eggs have both a sticker and a toy inside, that's why it's enough to buy only one egg.

In the third query, we have to buy both eggs: one with a sticker and one with a toy.

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 letters shop showcase is a string $$$s$$$, consisting of $$$n$$$ lowercase Latin letters. As the name tells, letters are sold in the shop.

Letters are sold one by one from the leftmost to the rightmost. Any customer can only buy some prefix of letters from the string $$$s$$$.

There are $$$m$$$ friends, the $$$i$$$-th of them is named $$$t_i$$$. Each of them is planning to estimate the following value: how many letters (the length of the shortest prefix) would s/he need to buy if s/he wanted to construct her/his name of bought letters. The name can be constructed if each letter is presented in the equal or greater amount.

- For example, for $$$s$$$="arrayhead" and $$$t_i$$$="arya" $$$5$$$ letters have to be bought ("arrayhead").
- For example, for $$$s$$$="arrayhead" and $$$t_i$$$="harry" $$$6$$$ letters have to be bought ("arrayhead").
- For example, for $$$s$$$="arrayhead" and $$$t_i$$$="ray" $$$5$$$ letters have to be bought ("arrayhead").
- For example, for $$$s$$$="arrayhead" and $$$t_i$$$="r" $$$2$$$ letters have to be bought ("arrayhead").
- For example, for $$$s$$$="arrayhead" and $$$t_i$$$="areahydra" all $$$9$$$ letters have to be bought ("arrayhead").

It is guaranteed that every friend can construct her/his name using the letters from the string $$$s$$$.

Note that the values for friends are independent, friends are only estimating them but not actually buying the letters.

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

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

The third line contains one integer $$$m$$$ ($$$1 \le m \le 5 \cdot 10^4$$$) — the number of friends.

The $$$i$$$-th of the next $$$m$$$ lines contains $$$t_i$$$ ($$$1 \le |t_i| \le 2 \cdot 10^5$$$) — the name of the $$$i$$$-th friend.

It is guaranteed that $$$\sum \limits_{i=1}^m |t_i| \le 2 \cdot 10^5$$$.

## Output Format
For each friend print the length of the shortest prefix of letters from $$$s$$$ s/he would need to buy to be able to construct her/his name of them. The name can be constructed if each letter is presented in the equal or greater amount.

It is guaranteed that every friend can construct her/his name using the letters from the string $$$s$$$.

## Examples
```input
9
arrayhead
5
arya
harry
ray
r
areahydra
```
```output
5
6
5
2
9
```

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 an array $$$a_1, a_2, \dots, a_n$$$.

You don't know this array, but he told you $$$m$$$ facts about this array. The $$$i$$$-th fact is a triple of numbers $$$t_i$$$, $$$l_i$$$ and $$$r_i$$$ ($$$0 \le t_i \le 1, 1 \le l_i < r_i \le n$$$) and it means:

- if $$$t_i=1$$$ then subbarray $$$a_{l_i}, a_{l_i + 1}, \dots, a_{r_i}$$$ is sorted in non-decreasing order;
- if $$$t_i=0$$$ then subbarray $$$a_{l_i}, a_{l_i + 1}, \dots, a_{r_i}$$$ is not sorted in non-decreasing order. A subarray is not sorted if there is at least one pair of consecutive elements in this subarray such that the former is greater than the latter.

For example if $$$a = [2, 1, 1, 3, 2]$$$ then he could give you three facts: $$$t_1=1, l_1=2, r_1=4$$$ (the subarray $$$[a_2, a_3, a_4] = [1, 1, 3]$$$ is sorted), $$$t_2=0, l_2=4, r_2=5$$$ (the subarray $$$[a_4, a_5] = [3, 2]$$$ is not sorted), and $$$t_3=0, l_3=3, r_3=5$$$ (the subarray $$$[a_3, a_5] = [1, 3, 2]$$$ is not sorted).

You don't know the array $$$a$$$. Find any array which satisfies all the given facts.

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 1000, 1 \le m \le 1000$$$).

Each of the next $$$m$$$ lines contains three integers $$$t_i$$$, $$$l_i$$$ and $$$r_i$$$ ($$$0 \le t_i \le 1, 1 \le l_i < r_i \le n$$$).

If $$$t_i = 1$$$ then subbarray $$$a_{l_i}, a_{l_i + 1}, \dots , a_{r_i}$$$ is sorted. Otherwise (if $$$t_i = 0$$$) subbarray $$$a_{l_i}, a_{l_i + 1}, \dots , a_{r_i}$$$ is not sorted.

## Output Format
If there is no array that satisfies these facts in only line print NO (in any letter case).

If there is a solution, print YES (in any letter case). In second line print $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the array $$$a$$$, satisfying all the given facts. If there are multiple satisfying arrays you can print any of them.

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

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 are given an array $$$a_1, a_2, \dots, a_n$$$ and an array $$$b_1, b_2, \dots, b_n$$$.

For one operation you can sort in non-decreasing order any subarray $$$a[l \dots r]$$$ of the array $$$a$$$.

For example, if $$$a = [4, 2, 2, 1, 3, 1]$$$ and you choose subbarray $$$a[2 \dots 5]$$$, then the array turns into $$$[4, 1, 2, 2, 3, 1]$$$.

You are asked to determine whether it is possible to obtain the array $$$b$$$ by applying this operation any number of times (possibly zero) to the array $$$a$$$.

## Input Format
The first line contains one integer $$$t$$$ ($$$1 \le t \le 3 \cdot 10^5$$$) — the number of queries.

The first line of each query contains one integer $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$).

The second line of each query contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$).

The third line of each query contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_i \le n$$$).

It is guaranteed that $$$\sum n \le 3 \cdot 10^5$$$ over all queries in a test.

## Output Format
For each query print YES (in any letter case) if it is possible to obtain an array $$$b$$$ and NO (in any letter case) otherwise.

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

## Note
In first test case the can sort subarray $$$a_1 \dots a_5$$$, then $$$a$$$ will turn into $$$[1, 1, 4, 4, 7, 5, 6]$$$, and then sort subarray $$$a_5 \dots a_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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
You are given a tree (an undirected connected acyclic graph) consisting of $$$n$$$ vertices. You are playing a game on this tree.

Initially all vertices are white. On the first turn of the game you choose one vertex and paint it black. Then on each turn you choose a white vertex adjacent (connected by an edge) to any black vertex and paint it black.

Each time when you choose a vertex (even during the first turn), you gain the number of points equal to the size of the connected component consisting only of white vertices that contains the chosen vertex. The game ends when all vertices are painted black.

Let's see the following example:

Vertices $$$1$$$ and $$$4$$$ are painted black already. If you choose the vertex $$$2$$$, you will gain $$$4$$$ points for the connected component consisting of vertices $$$2, 3, 5$$$ and $$$6$$$. If you choose the vertex $$$9$$$, you will gain $$$3$$$ points for the connected component consisting of vertices $$$7, 8$$$ and $$$9$$$.

Your task is to maximize the number of points you gain.

## Input Format
The first line contains an integer $$$n$$$ — the number of vertices in the tree ($$$2 \le n \le 2 \cdot 10^5$$$).

Each of the next $$$n - 1$$$ lines describes an edge of the tree. Edge $$$i$$$ is denoted by two integers $$$u_i$$$ and $$$v_i$$$, the indices of vertices it connects ($$$1 \le u_i, v_i \le n$$$, $$$u_i \ne v_i$$$).

It is guaranteed that the given edges form a tree.

## Output Format
Print one integer — the maximum number of points you gain if you will play optimally.

## Examples
```input
9
1 2
2 3
2 5
2 6
1 4
4 9
9 7
9 8
```
```output
36
```
-----
```input
5
1 2
1 3
2 4
2 5
```
```output
14
```

## Note
The first example tree is shown in the problem statement.

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
Let $$$x$$$ be an array of integers $$$x = [x_1, x_2, \dots, x_n]$$$. Let's define $$$B(x)$$$ as a minimal size of a partition of $$$x$$$ into subsegments such that all elements in each subsegment are equal. For example, $$$B([3, 3, 6, 1, 6, 6, 6]) = 4$$$ using next partition: $$$[3, 3\ |\ 6\ |\ 1\ |\ 6, 6, 6]$$$.

Now you don't have any exact values of $$$x$$$, but you know that $$$x_i$$$ can be any integer value from $$$[l_i, r_i]$$$ ($$$l_i \le r_i$$$) uniformly at random. All $$$x_i$$$ are independent.

Calculate expected value of $$$(B(x))^2$$$, or $$$E((B(x))^2)$$$. It's guaranteed that the expected value can be represented as rational fraction $$$\frac{P}{Q}$$$ where $$$(P, Q) = 1$$$, so print the value $$$P \cdot Q^{-1} \mod 10^9 + 7$$$.

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

The second line contains $$$n$$$ integers $$$l_1, l_2, \dots, l_n$$$ ($$$1 \le l_i \le 10^9$$$).

The third line contains $$$n$$$ integers $$$r_1, r_2, \dots, r_n$$$ ($$$l_i \le r_i \le 10^9$$$).

## Output Format
Print the single integer — $$$E((B(x))^2)$$$ as $$$P \cdot Q^{-1} \mod 10^9 + 7$$$.

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

## Note
Let's describe all possible values of $$$x$$$ for the first sample:

- $$$[1, 1, 1]$$$: $$$B(x) = 1$$$, $$$B^2(x) = 1$$$;
- $$$[1, 1, 2]$$$: $$$B(x) = 2$$$, $$$B^2(x) = 4$$$;
- $$$[1, 1, 3]$$$: $$$B(x) = 2$$$, $$$B^2(x) = 4$$$;
- $$$[1, 2, 1]$$$: $$$B(x) = 3$$$, $$$B^2(x) = 9$$$;
- $$$[1, 2, 2]$$$: $$$B(x) = 2$$$, $$$B^2(x) = 4$$$;
- $$$[1, 2, 3]$$$: $$$B(x) = 3$$$, $$$B^2(x) = 9$$$;

All possible values of $$$x$$$ for the second sample:

- $$$[3, 4, 5]$$$: $$$B(x) = 3$$$, $$$B^2(x) = 9$$$;
- $$$[3, 4, 6]$$$: $$$B(x) = 3$$$, $$$B^2(x) = 9$$$;
- $$$[3, 5, 5]$$$: $$$B(x) = 2$$$, $$$B^2(x) = 4$$$;
- $$$[3, 5, 6]$$$: $$$B(x) = 3$$$, $$$B^2(x) = 9$$$;
- $$$[4, 4, 5]$$$: $$$B(x) = 2$$$, $$$B^2(x) = 4$$$;
- $$$[4, 4, 6]$$$: $$$B(x) = 2$$$, $$$B^2(x) = 4$$$;
- $$$[4, 5, 5]$$$: $$$B(x) = 2$$$, $$$B^2(x) = 4$$$;
- $$$[4, 5, 6]$$$: $$$B(x) = 3$$$, $$$B^2(x) = 9$$$;

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 string $$$s$$$ — a sequence of commands for your toy robot. The robot is placed in some cell of a rectangular grid. He can perform four commands:

- 'W' — move one cell up;
- 'S' — move one cell down;
- 'A' — move one cell left;
- 'D' — move one cell right.

Let $$$Grid(s)$$$ be the grid of minimum possible area such that there is a position in the grid where you can place the robot in such a way that it will not fall from the grid while running the sequence of commands $$$s$$$. For example, if $$$s = \text{DSAWWAW}$$$ then $$$Grid(s)$$$ is the $$$4 \times 3$$$ grid:

1. you can place the robot in the cell $$$(3, 2)$$$;
2. the robot performs the command 'D' and moves to $$$(3, 3)$$$;
3. the robot performs the command 'S' and moves to $$$(4, 3)$$$;
4. the robot performs the command 'A' and moves to $$$(4, 2)$$$;
5. the robot performs the command 'W' and moves to $$$(3, 2)$$$;
6. the robot performs the command 'W' and moves to $$$(2, 2)$$$;
7. the robot performs the command 'A' and moves to $$$(2, 1)$$$;
8. the robot performs the command 'W' and moves to $$$(1, 1)$$$.

You have $$$4$$$ extra letters: one 'W', one 'A', one 'S', one 'D'. You'd like to insert at most one of these letters in any position of sequence $$$s$$$ to minimize the area of $$$Grid(s)$$$.

What is the minimum area of $$$Grid(s)$$$ you can achieve?

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

Next $$$T$$$ lines contain queries: one per line. This line contains single string $$$s$$$ ($$$1 \le |s| \le 2 \cdot 10^5$$$, $$$s_i \in \{\text{W}, \text{A}, \text{S}, \text{D}\}$$$) — the sequence of commands.

It's guaranteed that the total length of $$$s$$$ over all queries doesn't exceed $$$2 \cdot 10^5$$$.

## Output Format
Print $$$T$$$ integers: one per query. For each query print the minimum area of $$$Grid(s)$$$ you can achieve.

## Examples
```input
3
DSAWWAW
D
WA
```
```output
8
2
4
```

## Note
In the first query you have to get string $$$\text{DSAWW}\underline{D}\text{AW}$$$.

In second and third queries you can not decrease the area of $$$Grid(s)$$$.

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 $$$t$$$ and $$$n$$$ strings $$$s_1, s_2, \dots, s_n$$$. All strings consist of lowercase Latin letters.

Let $$$f(t, s)$$$ be the number of occurences of string $$$s$$$ in string $$$t$$$. For example, $$$f('\text{aaabacaa}', '\text{aa}') = 3$$$, and $$$f('\text{ababa}', '\text{aba}') = 2$$$.

Calculate the value of $$$\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} f(t, s_i + s_j)$$$, where $$$s + t$$$ is the concatenation of strings $$$s$$$ and $$$t$$$. Note that if there are two pairs $$$i_1$$$, $$$j_1$$$ and $$$i_2$$$, $$$j_2$$$ such that $$$s_{i_1} + s_{j_1} = s_{i_2} + s_{j_2}$$$, you should include both $$$f(t, s_{i_1} + s_{j_1})$$$ and $$$f(t, s_{i_2} + s_{j_2})$$$ in answer.

## Input Format
The first line contains string $$$t$$$ ($$$1 \le |t| \le 2 \cdot 10^5$$$).

The second line contains integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$).

Each of next $$$n$$$ lines contains string $$$s_i$$$ ($$$1 \le |s_i| \le 2 \cdot 10^5$$$).

It is guaranteed that $$$\sum\limits_{i=1}^{n} |s_i| \le 2 \cdot 10^5$$$. All strings consist of lowercase English letters.

## Output Format
Print one integer — the value of $$$\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} f(t, s_i + s_j)$$$.

## Examples
```input
aaabacaa
2
a
aa
```
```output
5
```
-----
```input
aaabacaa
4
a
a
a
b
```
```output
33
```

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$$$ uppercase Latin letters 'A' and $$$b$$$ letters 'B'.

The period of the string is the smallest such positive integer $$$k$$$ that $$$s_i = s_{i~mod~k}$$$ ($$$0$$$-indexed) for each $$$i$$$. Note that this implies that $$$k$$$ won't always divide $$$a+b = |s|$$$.

For example, the period of string "ABAABAA" is $$$3$$$, the period of "AAAA" is $$$1$$$, and the period of "AABBB" is $$$5$$$.

Find the number of different periods over all possible strings with $$$a$$$ letters 'A' and $$$b$$$ letters 'B'.

## Input Format
The first line contains two integers $$$a$$$ and $$$b$$$ ($$$1 \le a, b \le 10^9$$$) — the number of letters 'A' and 'B', respectively.

## Output Format
Print the number of different periods over all possible strings with $$$a$$$ letters 'A' and $$$b$$$ letters 'B'.

## Examples
```input
2 4
```
```output
4
```
-----
```input
5 3
```
```output
5
```

## Note
All the possible periods for the first example:

- $$$3$$$ "BBABBA"
- $$$4$$$ "BBAABB"
- $$$5$$$ "BBBAAB"
- $$$6$$$ "AABBBB"

All the possible periods for the second example:

- $$$3$$$ "BAABAABA"
- $$$5$$$ "BAABABAA"
- $$$6$$$ "BABAAABA"
- $$$7$$$ "BAABAAAB"
- $$$8$$$ "AAAAABBB"

Note that these are not the only possible strings for the given periods.

Now solve the problem and return the code.