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
Once upon a time, Petya had an array of integers $$$a$$$ of length $$$n$$$. But over time, the array itself was lost, and only $$$n-1$$$ results of comparisons of neighboring array elements remained. In other words, for every $$$i$$$ from $$$1$$$ to $$$n-1$$$, Petya knows exactly one of these three facts:

- $$$a_i < a_{i+1}$$$;
- $$$a_i = a_{i+1}$$$;
- $$$a_i > a_{i+1}$$$.

Petya wonders if it is possible to uniquely determine the result of comparing $$$a_1$$$ and $$$a_n$$$.

You have to help Petya determine the result of comparing $$$a_1$$$ and $$$a_n$$$ or report that the result cannot be determined unambiguously.

## Input Format
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 500$$$) — the number of test cases.

The only line of the test case contains the string $$$s$$$ ($$$1 \le |s| \le 100$$$), where $$$s_i$$$ is:

- <, if $$$a_i < a_{i + 1}$$$;
- >, if $$$a_i > a_{i + 1}$$$;
- =, if $$$a_i = a_{i + 1}$$$.

## Output Format
For each test case, print a single string equal to:

- <, if $$$a_1 < a_n$$$;
- >, if $$$a_1 > a_n$$$;
- =, if $$$a_1 = a_n$$$;
- ?, if it is impossible to uniquely determine the result of the comparison.

## Examples
```input
4
>>>
<><=<
=
<<==
```
```output
>
?
=
<
```

## Note
Consider the test cases of the example:

- in the first test case, it's easy to see that $$$a_1 > a_4$$$ since $$$a_1 > a_2 > a_3 > a_4$$$;
- in the second test case, both sequences $$$[1, 2, 0, 10, 10, 15]$$$ and $$$[10, 11, 1, 2, 2, 5]$$$ meet the constraints; in the first one, $$$a_1 < a_6$$$, and in the second one, $$$a_1 > a_6$$$, so it's impossible to compare $$$a_1$$$ and $$$a_6$$$;
- in the third test case, we already know that $$$a_1 = a_2$$$;
- in the fourth test case, it's easy to see that $$$a_3 = a_4 = a_5$$$, and $$$a_1 < a_2 < a_3$$$, so $$$a_1 < a_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: 2.0 seconds
Memory limit: 256.0 MB

# Problem
Let's say that two strings $$$s$$$ and $$$t$$$ rhyme if both strings have length at least $$$k$$$, and their last $$$k$$$ characters are equal. For example, if $$$k = 3$$$, the strings abcd and cebcd rhyme, the strings ab and ab don't rhyme, the strings aaaa and aaaaa rhyme, the strings abcd and abce don't rhyme.

You have $$$n$$$ pairs of strings $$$(s_i, t_i)$$$, and for each pair of strings you know, should they rhyme or should not.

Find all possible non-negative integer values for $$$k$$$ such that pairs that have to rhyme, rhyme and pairs that must not rhyme, don't rhyme.

## Input Format
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 1000$$$). Description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the number of string pairs.

Next $$$n$$$ lines contains descriptions of pairs — one per line. The $$$i$$$-th line contains space-separated strings $$$s_i$$$ and $$$t_i$$$ and marker $$$r_i$$$. Strings are non-empty, consist of lowercase Latin letters and each have length at most $$$2 \cdot 10^5$$$. The marker $$$r_i$$$ equals to $$$1$$$ if strings have to rhyme, or $$$0$$$ if they must not rhyme.

It's guaranteed that for each test case there is at least one pair with $$$r_i$$$ equal to $$$1$$$ and that the total length of all strings over all test cases doesn't exceed $$$4 \cdot 10^5$$$.

## Output Format
For each test case, firstly print integer $$$m$$$ — the number of possible non-negative integer values of $$$k$$$ such that pairs that have to rhyme, rhyme and pairs that must not rhyme, don't rhyme. Next, print all these values of $$$k$$$ (without repetitions). You can print them in any order.

## Examples
```input
3
1
kotlin heroes 1
2
join kotlin 1
episode eight 0
4
abc abcdef 0
xyz zzz 1
aaa bba 0
c d 0
```
```output
1
0
2
1 2
0
```

## Note
In the first test case, if $$$k$$$ is at least $$$1$$$ then kotlin and heroes don't rhyme.

In the second test case, for $$$k = 2$$$ join and kotlin rhyme, and episode and eight don't rhyme.

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
Kotlinforces is a web platfrom that hosts programming competitions.

The staff of Kotlinforces is asked to schedule $$$n$$$ programming competitions on the next $$$m$$$ days. Each competition is held in multiple stages; the regulations of the $$$i$$$-th competition state that this competition should consist of exactly $$$k_i$$$ stages, and each stage, starting from the second one, should be scheduled exactly $$$t_i$$$ days after the previous stage. In other words, if the first stage of the $$$i$$$-th competition is scheduled on day $$$x$$$, the second stage should be scheduled on day $$$x+t_i$$$, the third stage — on day $$$x+2t_i$$$, ..., the $$$k_i$$$-th stage (which is the last one) — on day $$$x+(k_i-1)t_i$$$.

All $$$n$$$ competitions should be scheduled in such a way that they start and finish during the next $$$m$$$ days, and on any of these $$$m$$$ days, at most one stage of one competition is held (two stages of different competitions should not be scheduled on the same day).

Is it possible to schedule all $$$n$$$ competitions to meet these constraints?

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 5000$$$) — the number of competitions and the number of days, respectively.

Then $$$n$$$ lines follow, each describing a competition which should be scheduled. The $$$i$$$-th line contains two integers $$$k_i$$$ and $$$t_i$$$ ($$$2 \le k_i \le 5000$$$; $$$1 \le t_i \le 2$$$) — the parameters of the $$$i$$$-th competition.

## Output Format
If it is impossible to schedule all $$$n$$$ competitions on the next $$$m$$$ days so that there is at most one stage during each day, print -1.

Otherwise, print $$$n$$$ integers. The $$$i$$$-th integer should represent the day when the first stage of the $$$i$$$-th competition is scheduled; days are numbered from $$$1$$$ to $$$m$$$. If there are multiple answers, print any of them.

## Examples
```input
3 7
3 2
2 2
2 2
```
```output
2 5 1
```
-----
```input
1 7
4 2
```
```output
1
```
-----
```input
1 7
5 2
```
```output
-1
```
-----
```input
2 4
2 1
2 2
```
```output
-1
```
-----
```input
2 5
2 1
2 2
```
```output
4 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
Andi and Budi were given an assignment to tidy up their bookshelf of $$$n$$$ books. Each book is represented by the book title — a string $$$s_i$$$ numbered from $$$1$$$ to $$$n$$$, each with length $$$m$$$. Andi really wants to sort the book lexicographically ascending, while Budi wants to sort it lexicographically descending.

Settling their fight, they decided to combine their idea and sort it asc-desc-endingly, where the odd-indexed characters will be compared ascendingly, and the even-indexed characters will be compared descendingly.

A string $$$a$$$ occurs before a string $$$b$$$ in asc-desc-ending order if and only if in the first position where $$$a$$$ and $$$b$$$ differ, the following holds:

- if it is an odd position, the string $$$a$$$ has a letter that appears earlier in the alphabet than the corresponding letter in $$$b$$$;
- if it is an even position, the string $$$a$$$ has a letter that appears later in the alphabet than the corresponding letter in $$$b$$$.

## Input Format
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \cdot m \leq 10^6$$$).

The $$$i$$$-th of the next $$$n$$$ lines contains a string $$$s_i$$$ consisting of $$$m$$$ uppercase Latin letters — the book title. The strings are pairwise distinct.

## Output Format
Output $$$n$$$ integers — the indices of the strings after they are sorted asc-desc-endingly.

## Examples
```input
5 2
AA
AB
BB
BA
AZ
```
```output
5 2 1 3 4
```

## Note
The following illustrates the first example.

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: 512.0 MB

# Problem
Mr. Chanek lives in a city represented as a plane. He wants to build an amusement park in the shape of a circle of radius $$$r$$$. The circle must touch the origin (point $$$(0, 0)$$$).

There are $$$n$$$ bird habitats that can be a photo spot for the tourists in the park. The $$$i$$$-th bird habitat is at point $$$p_i = (x_i, y_i)$$$.

Find the minimum radius $$$r$$$ of a park with at least $$$k$$$ bird habitats inside.

A point is considered to be inside the park if and only if the distance between $$$p_i$$$ and the center of the park is less than or equal to the radius of the park. Note that the center and the radius of the park do not need to be integers.

In this problem, it is guaranteed that the given input always has a solution with $$$r \leq 2 \cdot 10^5$$$.

## Input Format
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 10^5$$$, $$$1 \leq k \leq n$$$) — the number of bird habitats in the city and the number of bird habitats required to be inside the park.

The $$$i$$$-th of the next $$$n$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$0 \leq |x_i|, |y_i| \leq 10^5$$$) — the position of the $$$i$$$-th bird habitat.

## Output Format
Output a single real number $$$r$$$ denoting the minimum radius of a park with at least $$$k$$$ bird habitats inside. It is guaranteed that the given input always has a solution with $$$r \leq 2 \cdot 10^5$$$.

Your answer is considered correct if its absolute or relative error does not exceed $$$10^{-4}$$$.

Formally, let your answer be $$$a$$$, and the jury's answer be $$$b$$$. Your answer is accepted if and only if $$$\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-4}$$$.

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

## Note
In the first example, Mr. Chanek can put the center of the park at $$$(-3, -1)$$$ with radius $$$\sqrt{10} \approx 3.162$$$. It can be proven this is the minimum $$$r$$$.

The following illustrates the first example. The blue points represent bird habitats and the red circle represents the amusement park.

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
Denote a cyclic sequence of size $$$n$$$ as an array $$$s$$$ such that $$$s_n$$$ is adjacent to $$$s_1$$$. The segment $$$s[r, l]$$$ where $$$l < r$$$ is the concatenation of $$$s[r, n]$$$ and $$$s[1, l]$$$.

You are given an array $$$a$$$ consisting of $$$n$$$ integers. Define $$$b$$$ as the cyclic sequence obtained from concatenating $$$m$$$ copies of $$$a$$$. Note that $$$b$$$ has size $$$n \cdot m$$$.

You are given an integer $$$k$$$ where $$$k = 1$$$ or $$$k$$$ is a prime number. Find the number of different segments in $$$b$$$ where the sum of elements in the segment is divisible by $$$k$$$.

Two segments are considered different if the set of indices of the segments are different. For example, when $$$n = 3$$$ and $$$m = 2$$$, the set of indices for segment $$$s[2, 5]$$$ is $$$\{2, 3, 4, 5\}$$$, and for segment $$$s[5, 2]$$$ is $$$\{5, 6, 1, 2\}$$$. In particular, the segments $$$s[1, 6], s[2,1], \ldots, s[6, 5]$$$ are considered as the same segment.

Output the answer modulo $$$10^9 + 7$$$.

## Input Format
The first line contains three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$1 \leq n, m, k \leq 2 \cdot 10^5$$$, $$$k = 1$$$ or $$$k$$$ is a prime number).

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 2 \cdot 10^5$$$).

## Output Format
Output an integer denoting the number of different segments in $$$b$$$ where the sum of elements in the segment is divisible by $$$k$$$, modulo $$$10^9 + 7$$$.

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

## Note
In the first example, all valid segments are $$$[1,4]$$$, $$$[2, 3]$$$, $$$[3, 5]$$$, and $$$[4, 2]$$$.

In the second example, one of the valid segments is $$$[1, 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: 2.0 seconds
Memory limit: 512.0 MB

# Problem
Mr. Chanek has an integer represented by a string $$$s$$$. Zero or more digits have been erased and are denoted by the character _. There are also zero or more digits marked by the character X, meaning they're the same digit.

Mr. Chanek wants to count the number of possible integer $$$s$$$, where $$$s$$$ is divisible by $$$25$$$. Of course, $$$s$$$ must not contain any leading zero. He can replace the character _ with any digit. He can also replace the character X with any digit, but it must be the same for every character X.

As a note, a leading zero is any 0 digit that comes before the first nonzero digit in a number string in positional notation. For example, 0025 has two leading zeroes. An exception is the integer zero, (0 has no leading zero, but 0000 has three leading zeroes).

## Input Format
One line containing the string $$$s$$$ ($$$1 \leq |s| \leq 8$$$). The string $$$s$$$ consists of the characters 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, _, and X.

## Output Format
Output an integer denoting the number of possible integer $$$s$$$.

## Examples
```input
25
```
```output
1
```
-----
```input
_00
```
```output
9
```
-----
```input
_XX
```
```output
9
```
-----
```input
0
```
```output
1
```
-----
```input
0_25
```
```output
0
```

## Note
In the first example, the only possible $$$s$$$ is $$$25$$$.

In the second and third example, $$$s \in \{100, 200,300,400,500,600,700,800,900\}$$$.

In the fifth example, all possible $$$s$$$ will have at least one leading zero.

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: 512.0 MB

# Problem
There is a city park represented as a tree with $$$n$$$ attractions as its vertices and $$$n - 1$$$ rails as its edges. The $$$i$$$-th attraction has happiness value $$$a_i$$$.

Each rail has a color. It is either black if $$$t_i = 0$$$, or white if $$$t_i = 1$$$. Black trains only operate on a black rail track, and white trains only operate on a white rail track. If you are previously on a black train and want to ride a white train, or you are previously on a white train and want to ride a black train, you need to use $$$1$$$ ticket.

The path of a tour must be a simple path — it must not visit an attraction more than once. You do not need a ticket the first time you board a train. You only have $$$k$$$ tickets, meaning you can only switch train types at most $$$k$$$ times. In particular, you do not need a ticket to go through a path consisting of one rail color.

Define $$$f(u, v)$$$ as the sum of happiness values of the attractions in the tour $$$(u, v)$$$, which is a simple path that starts at the $$$u$$$-th attraction and ends at the $$$v$$$-th attraction. Find the sum of $$$f(u,v)$$$ for all valid tours $$$(u, v)$$$ ($$$1 \leq u \leq v \leq n$$$) that does not need more than $$$k$$$ tickets, modulo $$$10^9 + 7$$$.

## Input Format
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$, $$$0 \leq k \leq n-1$$$) — the number of attractions in the city park and the number of tickets you have.

The second line contains $$$n$$$ integers $$$a_1, a_2,\ldots, a_n$$$ ($$$0 \leq a_i \leq 10^9$$$) — the happiness value of each attraction.

The $$$i$$$-th of the next $$$n - 1$$$ lines contains three integers $$$u_i$$$, $$$v_i$$$, and $$$t_i$$$ ($$$1 \leq u_i, v_i \leq n$$$, $$$0 \leq t_i \leq 1$$$) — an edge between vertices $$$u_i$$$ and $$$v_i$$$ with color $$$t_i$$$. The given edges form a tree.

## Output Format
Output an integer denoting the total happiness value for all valid tours $$$(u, v)$$$ ($$$1 \leq u \leq v \leq n$$$), modulo $$$10^9 + 7$$$.

## Examples
```input
5 0
1 3 2 6 4
1 2 1
1 4 0
3 2 1
2 5 0
```
```output
45
```
-----
```input
3 1
1 1 1
1 2 1
3 2 0
```
```output
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 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
Mr. Chanek opened a letter from his fellow, who is currently studying at Singanesia. Here is what it says.

Define an array $$$b$$$ ($$$0 \leq b_i < k$$$) with $$$n$$$ integers. While there exists a pair $$$(i, j)$$$ such that $$$b_i \ne b_j$$$, do the following operation:

- Randomly pick a number $$$i$$$ satisfying $$$0 \leq i < n$$$. Note that each number $$$i$$$ has a probability of $$$\frac{1}{n}$$$ to be picked.
- Randomly Pick a number $$$j$$$ satisfying $$$0 \leq j < k$$$.
- Change the value of $$$b_i$$$ to $$$j$$$. It is possible for $$$b_i$$$ to be changed to the same value.

Denote $$$f(b)$$$ as the expected number of operations done to $$$b$$$ until all elements of $$$b$$$ are equal.

You are given two integers $$$n$$$ and $$$k$$$, and an array $$$a$$$ ($$$-1 \leq a_i < k$$$) of $$$n$$$ integers.

For every index $$$i$$$ with $$$a_i = -1$$$, replace $$$a_i$$$ with a random number $$$j$$$ satisfying $$$0 \leq j < k$$$. Let $$$c$$$ be the number of occurrences of $$$-1$$$ in $$$a$$$. There are $$$k^c$$$ possibilites of $$$a$$$ after the replacement, each with equal probability of being the final array.

Find the expected value of $$$f(a)$$$ modulo $$$10^9 + 7$$$.

Formally, let $$$M = 10^9 + 7$$$. It can be shown that the answer can be expressed as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q \not \equiv 0 \pmod{M}$$$. Output the integer equal to $$$p \cdot q^{-1} \bmod M$$$. In other words, output such an integer $$$x$$$ that $$$0 \le x < M$$$ and $$$x \cdot q \equiv p \pmod{M}$$$.

After reading the letter, Mr. Chanek gave the task to you. Solve it for the sake of their friendship!

## Input Format
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$2 \leq n \leq 10^5$$$, $$$2 \leq k \leq 10^9$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-1 \leq a_i < k$$$).

## Output Format
Output an integer denoting the expected value of $$$f(a)$$$ modulo $$$10^9 + 7$$$.

## Examples
```input
2 2
0 1
```
```output
2
```
-----
```input
2 2
0 -1
```
```output
1
```
-----
```input
3 3
0 1 1
```
```output
12
```
-----
```input
3 3
-1 -1 -1
```
```output
11
```
-----
```input
10 9
-1 0 -1 1 1 2 2 3 3 3
```
```output
652419213
```

Now solve the problem and return the code.