vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Acacius is studying strings theory. Today he came with the following problem.

You are given a string $s$ of length $n$ consisting of lowercase English letters and question marks. It is possible to replace question marks with lowercase English letters in such a way that a string "abacaba" occurs as a substring in a resulting string exactly once?

Each question mark should be replaced with exactly one lowercase English letter. For example, string "a?b?c" can be transformed into strings "aabbc" and "azbzc", but can't be transformed into strings "aabc", "a?bbc" and "babbc".

Occurrence of a string $t$ of length $m$ in the string $s$ of length $n$ as a substring is a index $i$ ($1 \leq i \leq n - m + 1$) such that string $s[i..i+m-1]$ consisting of $m$ consecutive symbols of $s$ starting from $i$-th equals to string $t$. For example string "ababa" has two occurrences of a string "aba" as a substring with $i = 1$ and $i = 3$, but there are no occurrences of a string "aba" in the string "acba" as a substring.

Please help Acacius to check if it is possible to replace all question marks with lowercase English letters in such a way that a string "abacaba" occurs as a substring in a resulting string exactly once.


-----Input-----

First line of input contains an integer $T$ ($1 \leq T \leq 5000$), number of test cases. $T$ pairs of lines with test case descriptions follow.

The first line of a test case description contains a single integer $n$ ($7 \leq n \leq 50$), length of a string $s$.

The second line of a test case description contains string $s$ of length $n$ consisting of lowercase English letters and question marks.


-----Output-----

For each test case output an answer for it.

In case if there is no way to replace question marks in string $s$ with a lowercase English letters in such a way that there is exactly one occurrence of a string "abacaba" in the resulting string as a substring output "No".

Otherwise output "Yes" and in the next line output a resulting string consisting of $n$ lowercase English letters. If there are multiple possible strings, output any.

You may print every letter in "Yes" and "No" in any case you want (so, for example, the strings yEs, yes, Yes, and YES will all be recognized as positive answer).


-----Example-----
Input
6
7
abacaba
7
???????
11
aba?abacaba
11
abacaba?aba
15
asdf???f???qwer
11
abacabacaba

Output
Yes
abacaba
Yes
abacaba
Yes
abadabacaba
Yes
abacabadaba
No
No



-----Note-----

In first example there is exactly one occurrence of a string "abacaba" in the string "abacaba" as a substring.

In second example seven question marks can be replaced with any seven lowercase English letters and with "abacaba" in particular.

In sixth example there are two occurrences of a string "abacaba" as a substring.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
# Task

Write a function named `sumEvenNumbers`, taking a sequence of numbers as single parameter. Your function must return the sum of **the even values** of this sequence.

Only numbers without decimals like `4` or `4.0` can be even. 

## Input
* sequence of numbers: those numbers could be integers and/or floats. 


For example, considering this input value : `[4,3,1,2,5,10,6,7,9,8]`, then your function should return `30` (because `4 + 2 + 10 + 6 + 8 = 30`).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: 3-cycles

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
During a recent research Berland scientists found out that there were *n* cities in Ancient Berland, joined by two-way paths. Any two cities are joined by no more than one path. No path joins a city with itself. According to a well-known tradition, the road network was built so that it would be impossible to choose three cities from each of which one can get to any other one directly. That is, there was no cycle exactly as long as 3. Unfortunately, the road map has not been preserved till nowadays. Now the scientists are interested how much developed a country Ancient Berland was. Help them - find, what maximal number of roads could be in the country. You also have to restore any of the possible road maps.

Input Specification:
The first line contains an integer *n* (1<=≤<=*n*<=≤<=100) — the number of cities in Berland.

Output Specification:
On the first line must be printed number *m* — the maximal number of roads in Berland. Then print *m* lines containing two numbers each — the numbers of cities that the given road joins. The cities are numbered with integers from 1 to *n*. If there are several variants of solving the problem, print any of them.

Demo Input:
['3\n', '4\n']

Demo Output:
['2\n1 2\n2 3\n', '4\n1 2\n2 3\n3 4\n4 1\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The well-known Fibonacci sequence F_0, F_1, F_2,…  is defined as follows: 

  * F_0 = 0, F_1 = 1. 
  * For each i ≥ 2: F_i = F_{i - 1} + F_{i - 2}. 



Given an increasing arithmetic sequence of positive integers with n elements: (a, a + d, a + 2⋅ d,…, a + (n - 1)⋅ d).

You need to find another increasing arithmetic sequence of positive integers with n elements (b, b + e, b + 2⋅ e,…, b + (n - 1)⋅ e) such that:

  * 0 < b, e < 2^{64}, 
  * for all 0≤ i < n, the decimal representation of a + i ⋅ d appears as substring in the last 18 digits of the decimal representation of F_{b + i ⋅ e} (if this number has less than 18 digits, then we consider all its digits). 

Input

The first line contains three positive integers n, a, d (1 ≤ n, a, d, a + (n - 1) ⋅ d < 10^6).

Output

If no such arithmetic sequence exists, print -1.

Otherwise, print two integers b and e, separated by space in a single line (0 < b, e < 2^{64}).

If there are many answers, you can output any of them.

Examples

Input


3 1 1


Output


2 1

Input


5 1 2


Output


19 5

Note

In the first test case, we can choose (b, e) = (2, 1), because F_2 = 1, F_3 = 2, F_4 = 3.

In the second test case, we can choose (b, e) = (19, 5) because:

  * F_{19} = 4181 contains 1; 
  * F_{24} = 46368 contains 3; 
  * F_{29} = 514229 contains 5; 
  * F_{34} = 5702887 contains 7; 
  * F_{39} = 63245986 contains 9. 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Substrings Sort

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You are given $n$ strings. Each string consists of lowercase English letters. Rearrange (reorder) the given strings in such a way that for every string, all strings that are placed before it are its substrings.

String $a$ is a substring of string $b$ if it is possible to choose several consecutive letters in $b$ in such a way that they form $a$. For example, string "for" is contained as a substring in strings "codeforces", "for" and "therefore", but is not contained as a substring in strings "four", "fofo" and "rof".

Input Specification:
The first line contains an integer $n$ ($1 \le n \le 100$) — the number of strings.

The next $n$ lines contain the given strings. The number of letters in each string is from $1$ to $100$, inclusive. Each string consists of lowercase English letters.

Some strings might be equal.

Output Specification:
If it is impossible to reorder $n$ given strings in required order, print "NO" (without quotes).

Otherwise print "YES" (without quotes) and $n$ given strings in required order.

Demo Input:
['5\na\naba\nabacaba\nba\naba\n', '5\na\nabacaba\nba\naba\nabab\n', '3\nqwerty\nqwerty\nqwerty\n']

Demo Output:
['YES\na\nba\naba\naba\nabacaba\n', 'NO\n', 'YES\nqwerty\nqwerty\nqwerty\n']

Note:
In the second example you cannot reorder the strings because the string "abab" is not a substring of the string "abacaba".

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We need a function ```prime_bef_aft()``` that gives the largest prime below a certain given value ```n```, 

```befPrime or bef_prime``` (depending on the language), 

and the smallest prime larger than this value, 

```aftPrime/aft_prime``` (depending on the language).

The result should be output in a list like the following:

```python
prime_bef_aft(n) == [befPrime, aftPrime]
```

If n is a prime number it will give two primes, n will not be included in the result.

Let's see some cases:
```python
prime_bef_aft(100) == [97, 101]

prime_bef_aft(97) == [89, 101]

prime_bef_aft(101) == [97, 103]
```
Range for the random tests: 
```1000 <= n <= 200000```

(The extreme and special case n = 2 will not be considered for the tests. Thanks Blind4Basics)

Happy coding!!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A new pack of n t-shirts came to a shop. Each of the t-shirts is characterized by three integers p_{i}, a_{i} and b_{i}, where p_{i} is the price of the i-th t-shirt, a_{i} is front color of the i-th t-shirt and b_{i} is back color of the i-th t-shirt. All values p_{i} are distinct, and values a_{i} and b_{i} are integers from 1 to 3.

m buyers will come to the shop. Each of them wants to buy exactly one t-shirt. For the j-th buyer we know his favorite color c_{j}.

A buyer agrees to buy a t-shirt, if at least one side (front or back) is painted in his favorite color. Among all t-shirts that have colors acceptable to this buyer he will choose the cheapest one. If there are no such t-shirts, the buyer won't buy anything. Assume that the buyers come one by one, and each buyer is served only after the previous one is served.

You are to compute the prices each buyer will pay for t-shirts.


-----Input-----

The first line contains single integer n (1 ≤ n ≤ 200 000) — the number of t-shirts.

The following line contains sequence of integers p_1, p_2, ..., p_{n} (1 ≤ p_{i} ≤ 1 000 000 000), where p_{i} equals to the price of the i-th t-shirt.

The following line contains sequence of integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 3), where a_{i} equals to the front color of the i-th t-shirt.

The following line contains sequence of integers b_1, b_2, ..., b_{n} (1 ≤ b_{i} ≤ 3), where b_{i} equals to the back color of the i-th t-shirt.

The next line contains single integer m (1 ≤ m ≤ 200 000) — the number of buyers. 

The following line contains sequence c_1, c_2, ..., c_{m} (1 ≤ c_{j} ≤ 3), where c_{j} equals to the favorite color of the j-th buyer. The buyers will come to the shop in the order they are given in the input. Each buyer is served only after the previous one is served.

 


-----Output-----

Print to the first line m integers — the j-th integer should be equal to the price of the t-shirt which the j-th buyer will buy. If the j-th buyer won't buy anything, print -1.


-----Examples-----
Input
5
300 200 400 500 911
1 2 1 2 3
2 1 3 2 1
6
2 3 1 2 1 1

Output
200 400 300 500 911 -1 

Input
2
1000000000 1
1 1
1 2
2
2 1

Output
1 1000000000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Prime Problem

Time Limit: 1 seconds

Memory Limit: 256 megabytes

Problem Description:
In Berland prime numbers are fashionable — the respectable citizens dwell only on the floors with numbers that are prime numbers. The numismatists value particularly high the coins with prime nominal values. All the prime days are announced holidays!

Yet even this is not enough to make the Berland people happy. On the main street of the capital stand *n* houses, numbered from 1 to *n*. The government decided to paint every house a color so that the sum of the numbers of the houses painted every color is a prime number.

However it turned out that not all the citizens approve of this decision — many of them protest because they don't want many colored houses on the capital's main street. That's why it is decided to use the minimal possible number of colors. The houses don't have to be painted consecutively, but every one of *n* houses should be painted some color. The one-colored houses should not stand consecutively, any way of painting is acceptable.

There are no more than 5 hours left before the start of painting, help the government find the way when the sum of house numbers for every color is a prime number and the number of used colors is minimal.

Input Specification:
The single input line contains an integer *n* (2<=≤<=*n*<=≤<=6000) — the number of houses on the main streets of the capital.

Output Specification:
Print the sequence of *n* numbers, where the *i*-th number stands for the number of color for house number *i*. Number the colors consecutively starting from 1. Any painting order is allowed. If there are several solutions to that problem, print any of them. If there's no such way of painting print the single number -1.

Demo Input:
['8']

Demo Output:
['1 2 2 1 1 1 1 2']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array) and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).

Consider a permutation $p$ of length $n$, we build a graph of size $n$ using it as follows:   For every $1 \leq i \leq n$, find the largest $j$ such that $1 \leq j < i$ and $p_j > p_i$, and add an undirected edge between node $i$ and node $j$  For every $1 \leq i \leq n$, find the smallest $j$ such that $i < j \leq n$ and $p_j > p_i$, and add an undirected edge between node $i$ and node $j$ 

In cases where no such $j$ exists, we make no edges. Also, note that we make edges between the corresponding indices, not the values at those indices.

For clarity, consider as an example $n = 4$, and $p = [3,1,4,2]$; here, the edges of the graph are $(1,3),(2,1),(2,3),(4,3)$.

A permutation $p$ is cyclic if the graph built using $p$ has at least one simple cycle. 

Given $n$, find the number of cyclic permutations of length $n$. Since the number may be very large, output it modulo $10^9+7$.

Please refer to the Notes section for the formal definition of a simple cycle


-----Input-----

The first and only line contains a single integer $n$ ($3 \le n \le 10^6$).


-----Output-----

Output a single integer $0 \leq x < 10^9+7$, the number of cyclic permutations of length $n$ modulo $10^9+7$.


-----Examples-----
Input
4

Output
16
Input
583291

Output
135712853


-----Note-----

There are $16$ cyclic permutations for $n = 4$. $[4,2,1,3]$ is one such permutation, having a cycle of length four: $4 \rightarrow 3 \rightarrow 2 \rightarrow 1 \rightarrow 4$.

Nodes $v_1$, $v_2$, $\ldots$, $v_k$ form a simple cycle if the following conditions hold:   $k \geq 3$.  $v_i \neq v_j$ for any pair of indices $i$ and $j$. ($1 \leq i < j \leq k$)  $v_i$ and $v_{i+1}$ share an edge for all $i$ ($1 \leq i < k$), and $v_1$ and $v_k$ share an edge.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
# Task
 Consider the following ciphering algorithm:
```
For each character replace it with its code.
Concatenate all of the obtained numbers.
```
Given a ciphered string, return the initial one if it is known that it consists only of lowercase letters.

 Note: here the character's code means its `decimal ASCII code`, the numerical representation of a character used by most modern programming languages.

# Example

 For `cipher = "10197115121"`, the output should be `"easy"`.

 Explanation: 
 ```
 charCode('e') = 101, 
 charCode('a') = 97, 
 charCode('s') = 115 
 charCode('y') = 121.
```
# Input/Output


 - `[input]` string `cipher`

   A non-empty string which is guaranteed to be a cipher for some other string of lowercase letters.


 - `[output]` a string

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have a root tree containing n vertexes. Let's number the tree vertexes with integers from 1 to n. The tree root is in the vertex 1.

Each vertex (except fot the tree root) v has a direct ancestor pv. Also each vertex v has its integer value sv. 

Your task is to perform following queries:

  * P v u (u ≠ v). If u isn't in subtree of v, you must perform the assignment pv = u. Otherwise you must perform assignment pu = v. Note that after this query the graph continues to be a tree consisting of n vertexes.
  * V v t. Perform assignment sv = t. 



Your task is following. Before starting performing queries and after each query you have to calculate expected value written on the lowest common ancestor of two equiprobably selected vertices i and j. Here lowest common ancestor of i and j is the deepest vertex that lies on the both of the path from the root to vertex i and the path from the root to vertex j. Please note that the vertices i and j can be the same (in this case their lowest common ancestor coincides with them).

Input

The first line of the input contains integer n (2 ≤ n ≤ 5·104) — the number of the tree vertexes. 

The second line contains n - 1 integer p2, p3, ..., pn (1 ≤ pi ≤ n) — the description of the tree edges. It is guaranteed that those numbers form a tree.

The third line contains n integers — s1, s2, ... sn (0 ≤ si ≤ 106) — the values written on each vertex of the tree.

The next line contains integer q (1 ≤ q ≤ 5·104) — the number of queries. Each of the following q lines contains the description of the query in the format described in the statement. It is guaranteed that query arguments u and v lie between 1 and n. It is guaranteed that argument t in the queries of type V meets limits 0 ≤ t ≤ 106.

Output

Print q + 1 number — the corresponding expected values. Your answer will be considered correct if its absolute or relative error doesn't exceed 10 - 9.

Examples

Input

5
1 2 2 1
1 2 3 4 5
5
P 3 4
P 4 5
V 2 3
P 5 2
P 1 4


Output

1.640000000
1.800000000
2.280000000
2.320000000
2.800000000
1.840000000

Note

Note that in the query P v u if u lies in subtree of v you must perform assignment pu = v. An example of such case is the last query in the sample.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an array $a$ consisting of $n$ positive integers. You have to choose a positive integer $d$ and paint all elements into two colors. All elements which are divisible by $d$ will be painted red, and all other elements will be painted blue.

The coloring is called beautiful if there are no pairs of adjacent elements with the same color in the array. Your task is to find any value of $d$ which yields a beautiful coloring, or report that it is impossible.


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of testcases.

The first line of each testcase contains one integer $n$ ($2 \le n \le 100$) — the number of elements of the array.

The second line of each testcase contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^{18}$).


-----Output-----

For each testcase print a single integer. If there is no such value of $d$ that yields a beautiful coloring, print $0$. Otherwise, print any suitable value of $d$ ($1 \le d \le 10^{18}$).


-----Examples-----

Input
5
5
1 2 3 4 5
3
10 5 15
3
100 10 200
10
9 8 2 6 6 2 8 6 5 4
2
1 3
Output
2
0
100
0
3


-----Note-----

None

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a staircase with N steps. Takahashi is now standing at the foot of the stairs, that is, on the 0-th step.
He can climb up one or two steps at a time.
However, the treads of the a_1-th, a_2-th, a_3-th, \ldots, a_M-th steps are broken, so it is dangerous to set foot on those steps.
How many are there to climb up to the top step, that is, the N-th step, without setting foot on the broken steps?
Find the count modulo 1\ 000\ 000\ 007.

-----Constraints-----
 - 1 \leq N \leq 10^5
 - 0 \leq M \leq N-1
 - 1 \leq a_1 < a_2 <  ...  < a_M \leq N-1

-----Input-----
Input is given from Standard Input in the following format:
N M
a_1
a_2
 .
 .
 .
a_M

-----Output-----
Print the number of ways to climb up the stairs under the condition, modulo 1\ 000\ 000\ 007.

-----Sample Input-----
6 1
3

-----Sample Output-----
4

There are four ways to climb up the stairs, as follows:
 - 0 \to 1 \to 2 \to 4 \to 5 \to 6
 - 0 \to 1 \to 2 \to 4 \to 6
 - 0 \to 2 \to 4 \to 5 \to 6
 - 0 \to 2 \to 4 \to 6

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Truncate the given string (first argument) if it is longer than the given maximum length (second argument). Return the truncated string with a `"..."` ending.

Note that inserting the three dots to the end will add to the string length.

However, if the given maximum string length num is less than or equal to 3, then the addition of the three dots does not add to the string length in determining the truncated string.


## Examples
```
('codewars', 9)  ==>  'codewars'
('codewars', 7)  ==>  'code...'
('codewars', 2)  ==>  'co...'
```

[Taken from FCC](https://www.freecodecamp.com/challenges/truncate-a-string)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Luba thinks about watering her garden. The garden can be represented as a segment of length k. Luba has got n buckets, the i-th bucket allows her to water some continuous subsegment of garden of length exactly a_{i} each hour. Luba can't water any parts of the garden that were already watered, also she can't water the ground outside the garden.

Luba has to choose one of the buckets in order to water the garden as fast as possible (as mentioned above, each hour she will water some continuous subsegment of length a_{i} if she chooses the i-th bucket). Help her to determine the minimum number of hours she has to spend watering the garden. It is guaranteed that Luba can always choose a bucket so it is possible water the garden.

See the examples for better understanding.


-----Input-----

The first line of input contains two integer numbers n and k (1 ≤ n, k ≤ 100) — the number of buckets and the length of the garden, respectively.

The second line of input contains n integer numbers a_{i} (1 ≤ a_{i} ≤ 100) — the length of the segment that can be watered by the i-th bucket in one hour.

It is guaranteed that there is at least one bucket such that it is possible to water the garden in integer number of hours using only this bucket.


-----Output-----

Print one integer number — the minimum number of hours required to water the garden.


-----Examples-----
Input
3 6
2 3 5

Output
2

Input
6 7
1 2 3 4 5 6

Output
7



-----Note-----

In the first test the best option is to choose the bucket that allows to water the segment of length 3. We can't choose the bucket that allows to water the segment of length 5 because then we can't water the whole garden.

In the second test we can choose only the bucket that allows us to water the segment of length 1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given are integer sequence of length N, A = (A_1, A_2, \cdots, A_N), and an integer K.
For each X such that 1 \le X \le K, find the following value:
\left(\displaystyle \sum_{L=1}^{N-1} \sum_{R=L+1}^{N} (A_L+A_R)^X\right) \bmod 998244353

-----Constraints-----
 - All values in input are integers.
 -  2 \le N \le 2 \times 10^5
 -  1 \le K \le 300 
 -  1 \le A_i \le 10^8 

-----Input-----
Input is given from Standard Input in the following format:
N K
A_1 A_2 \cdots A_N

-----Output-----
Print K lines.
The X-th line should contain the value \left(\displaystyle \sum_{L=1}^{N-1} \sum_{R=L+1}^{N} (A_L+A_R)^X \right) \bmod 998244353.

-----Sample Input-----
3 3
1 2 3

-----Sample Output-----
12
50
216

In the 1-st line, we should print (1+2)^1 + (1+3)^1 + (2+3)^1 = 3 + 4 + 5 = 12.
In the 2-nd line, we should print (1+2)^2 + (1+3)^2 + (2+3)^2 = 9 + 16 + 25 = 50.
In the 3-rd line, we should print (1+2)^3 + (1+3)^3 + (2+3)^3 = 27 + 64 + 125 = 216.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.