vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Given an array $A$ of length $N$, we can define rotation as follows. If we rotate $A$ to the right, all elements move to the right one unit, and the last element moves to the beginning. That is, it becomes $[A_{N}, A_{1},A_{2},\ldots,A_{N-1}]$. Similarly if we rotate $A$ to the left, it becomes $[A_{2},A_{3},\ldots,A_{N}, A_{1}]$.

Given an array $A$ and an integer $x$, define $f(A,x)$ to be the array $A$ rotated by the amount $x$. If $x≥ 0$, this means we rotate it right $x$ times. If $x<0$, this means we rotate it left $|x|$ times.

You are given an array $A$ of length $N$. Then $Q$ queries follow. In each query, an integer $x$ is given. To answer the query, you should replace $A$ with $A+f(A,x)$ where $+$ denotes concatenation. After this operation, you must output the sum of all elements of $A$. Since this number can be large, output it modulo $10^{9} + 7$.

Note that the queries are cumulative. When you modify $A$ to answer one query, it starts that way for the next query.

------ Input ------

The first line contains an integer $N$ - the size of the initial array. 
The second line contains $N$ integers $A_{1},\ldots, A_{N}$ - the elements of the initial array.
The third line contains an integer $Q$ - the number of queries.
The fourth line contains $Q$ space-separated integers $x_{1},\ldots, x_{Q}$, where $x_{i}$ is the parameter of the $i$-th query.

------ Output ------
After each query, output in a single line the the sum of all elements of the current array modulo $10^{9}+7$.

------ Constraints  ------
$ 1≤ N≤ 10^{5}$
$ 1≤ Q≤ 10^{5}$
$ -10^{9}≤ A_{i}≤ 10^{9}$ 
$ -10^{5} ≤ x_{i}≤ 10^{5}$ 

------ Subtasks ------

Subtask #1 (100 points): original constraints

----- Sample Input 1 ------ 
2
1 2
2
1 1
----- Sample Output 1 ------ 
6
12
----- explanation 1 ------ 
Initially, the array is $[1,2]$.
After the first query, the array becomes $[1, 2] + f([1, 2], 1) = [1, 2] + [2, 1] = [1, 2, 2, 1]$. The total sum is $6$.
After the second query, the array becomes $[1, 2, 2, 1] + f([1, 2, 2, 1], 1) = [1, 2, 2, 1] + [1, 1, 2, 2] = [1, 2, 2, 1, 1, 1, 2, 2]$. The total sum is $12$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Graph And Its Complement

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Given three numbers $n, a, b$. You need to find an adjacency matrix of such an undirected graph that the number of components in it is equal to $a$, and the number of components in its complement is $b$. The matrix must be symmetric, and all digits on the main diagonal must be zeroes.

In an undirected graph loops (edges from a vertex to itself) are not allowed. It can be at most one edge between a pair of vertices.

The adjacency matrix of an undirected graph is a square matrix of size $n$ consisting only of "0" and "1", where $n$ is the number of vertices of the graph and the $i$-th row and the $i$-th column correspond to the $i$-th vertex of the graph. The cell $(i,j)$ of the adjacency matrix contains $1$ if and only if the $i$-th and $j$-th vertices in the graph are connected by an edge.

A connected component is a set of vertices $X$ such that for every two vertices from this set there exists at least one path in the graph connecting this pair of vertices, but adding any other vertex to $X$ violates this rule.

The complement or inverse of a graph $G$ is a graph $H$ on the same vertices such that two distinct vertices of $H$ are adjacent if and only if they are not adjacent in $G$.

Input Specification:
In a single line, three numbers are given $n, a, b \,(1 \le n \le 1000, 1 \le a, b \le n)$: is the number of vertexes of the graph, the required number of connectivity components in it, and the required amount of the connectivity component in it's complement.

Output Specification:
If there is no graph that satisfies these constraints on a single line, print "NO" (without quotes).

Otherwise, on the first line, print "YES"(without quotes). In each of the next $n$ lines, output $n$ digits such that $j$-th digit of $i$-th line must be $1$ if and only if there is an edge between vertices $i$ and $j$ in $G$ (and $0$ otherwise). Note that the matrix must be symmetric, and all digits on the main diagonal must be zeroes. 

If there are several matrices that satisfy the conditions — output any of them.

Demo Input:
['3 1 2\n', '3 3 3\n']

Demo Output:
['YES\n001\n001\n110\n', 'NO\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a directed graph of n vertices and m edges. Vertices are numbered from 1 to n. There is a token in vertex 1.

The following actions are allowed: 

  * Token movement. To move the token from vertex u to vertex v if there is an edge u → v in the graph. This action takes 1 second. 
  * Graph transposition. To transpose all the edges in the graph: replace each edge u → v by an edge v → u. This action takes increasingly more time: k-th transposition takes 2^{k-1} seconds, i.e. the first transposition takes 1 second, the second one takes 2 seconds, the third one takes 4 seconds, and so on. 



The goal is to move the token from vertex 1 to vertex n in the shortest possible time. Print this time modulo 998 244 353.

Input

The first line of input contains two integers n, m (1 ≤ n, m ≤ 200 000).

The next m lines contain two integers each: u, v (1 ≤ u, v ≤ n; u ≠ v), which represent the edges of the graph. It is guaranteed that all ordered pairs (u, v) are distinct.

It is guaranteed that it is possible to move the token from vertex 1 to vertex n using the actions above.

Output

Print one integer: the minimum required time modulo 998 244 353.

Examples

Input


4 4
1 2
2 3
3 4
4 1


Output


2


Input


4 3
2 1
2 3
4 3


Output


10

Note

The first example can be solved by transposing the graph and moving the token to vertex 4, taking 2 seconds.

The best way to solve the second example is the following: transpose the graph, move the token to vertex 2, transpose the graph again, move the token to vertex 3, transpose the graph once more and move the token to vertex 4.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Akash has lots of assignments to submit in his college. In one of the assignment he is given a string S of length N consisting of lowercase letters (a - z) only. Akash has to answer Q queries and for every query, he is given L, R and K. For each query he has to find the lexicographically Kth smallest character in  substring of S starting from L to R, inclusively. Help Akash in solving his assignment.

Input

First line contains 2 integers N and Q, length of string and number of queries. Next line has a string S of length N. Next Q lines contains 3 integers L, R and K.

Output

For each query output the lexicographically Kth smallest character in substring of S starting from L to R if possible, else print "Out of range" (without qoutes).

Constraints

1 ≤ N ≤ 5*10^4

1 ≤ Q ≤ 10^5

1 ≤ L  ≤ R ≤ N

1 ≤ K ≤ N

Note:
S contains only lowercase latin letters (a to z).

SAMPLE INPUT
6 2
abcdef
2 6 3
4 6 1

SAMPLE OUTPUT
d
d

Explanation

In first query, substring will be bcdef. 3rd smallest character in the substring is d.
In second query, substring will be def. 1st smallest character in the substring is d.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Some days ago, WJMZBMR learned how to answer the query "how many times does a string x occur in a string s" quickly by preprocessing the string s. But now he wants to make it harder.

So he wants to ask "how many consecutive substrings of s are cyclical isomorphic to a given string x". You are given string s and n strings xi, for each string xi find, how many consecutive substrings of s are cyclical isomorphic to xi.

Two strings are called cyclical isomorphic if one can rotate one string to get the other one. 'Rotate' here means 'to take some consecutive chars (maybe none) from the beginning of a string and put them back at the end of the string in the same order'. For example, string "abcde" can be rotated to string "deabc". We can take characters "abc" from the beginning and put them at the end of "de".

Input

The first line contains a non-empty string s. The length of string s is not greater than 106 characters.

The second line contains an integer n (1 ≤ n ≤ 105) — the number of queries. Then n lines follow: the i-th line contains the string xi — the string for the i-th query. The total length of xi is less than or equal to 106 characters.

In this problem, strings only consist of lowercase English letters.

Output

For each query xi print a single integer that shows how many consecutive substrings of s are cyclical isomorphic to xi. Print the answers to the queries in the order they are given in the input.

Examples

Input

baabaabaaa
5
a
ba
baa
aabaa
aaba


Output

7
5
7
3
5


Input

aabbaa
3
aa
aabb
abba


Output

2
3
3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an array $d_1, d_2, \dots, d_n$ consisting of $n$ integer numbers.

Your task is to split this array into three parts (some of which may be empty) in such a way that each element of the array belongs to exactly one of the three parts, and each of the parts forms a consecutive contiguous subsegment (possibly, empty) of the original array. 

Let the sum of elements of the first part be $sum_1$, the sum of elements of the second part be $sum_2$ and the sum of elements of the third part be $sum_3$. Among all possible ways to split the array you have to choose a way such that $sum_1 = sum_3$ and $sum_1$ is maximum possible.

More formally, if the first part of the array contains $a$ elements, the second part of the array contains $b$ elements and the third part contains $c$ elements, then:

$$sum_1 = \sum\limits_{1 \le i \le a}d_i,$$ $$sum_2 = \sum\limits_{a + 1 \le i \le a + b}d_i,$$ $$sum_3 = \sum\limits_{a + b + 1 \le i \le a + b + c}d_i.$$

The sum of an empty array is $0$.

Your task is to find a way to split the array such that $sum_1 = sum_3$ and $sum_1$ is maximum possible.


-----Input-----

The first line of the input contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of elements in the array $d$.

The second line of the input contains $n$ integers $d_1, d_2, \dots, d_n$ ($1 \le d_i \le 10^9$) — the elements of the array $d$.


-----Output-----

Print a single integer — the maximum possible value of $sum_1$, considering that the condition $sum_1 = sum_3$ must be met.

Obviously, at least one valid way to split the array exists (use $a=c=0$ and $b=n$).


-----Examples-----
Input
5
1 3 1 1 4

Output
5

Input
5
1 3 2 1 4

Output
4

Input
3
4 1 2

Output
0



-----Note-----

In the first example there is only one possible splitting which maximizes $sum_1$: $[1, 3, 1], [~], [1, 4]$.

In the second example the only way to have $sum_1=4$ is: $[1, 3], [2, 1], [4]$.

In the third example there is only one way to split the array: $[~], [4, 1, 2], [~]$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The only difference between the easy and hard versions is that tokens of type O do not appear in the input of the easy version.

Errichto gave Monogon the following challenge in order to intimidate him from taking his top contributor spot on Codeforces.

In a Tic-Tac-Toe grid, there are n rows and n columns. Each cell of the grid is either empty or contains a token. There are two types of tokens: X and O. If there exist three tokens of the same type consecutive in a row or column, it is a winning configuration. Otherwise, it is a draw configuration.

<image> The patterns in the first row are winning configurations. The patterns in the second row are draw configurations. 

In an operation, you can change an X to an O, or an O to an X. Let k denote the total number of tokens in the grid. Your task is to make the grid a draw in at most ⌊ k/3⌋ (rounding down) operations.

You are not required to minimize the number of operations.

Input

The first line contains a single integer t (1≤ t≤ 100) — the number of test cases.

The first line of each test case contains a single integer n (1≤ n≤ 300) — the size of the grid.

The following n lines each contain a string of n characters, denoting the initial grid. The character in the i-th row and j-th column is '.' if the cell is empty, or it is the type of token in the cell: 'X' or 'O'.

It is guaranteed that not all cells are empty.

In the easy version, the character 'O' does not appear in the input.

The sum of n across all test cases does not exceed 300.

Output

For each test case, print the state of the grid after applying the operations.

We have proof that a solution always exists. If there are multiple solutions, print any.

Example

Input


3
3
.X.
XXX
.X.
6
XX.XXX
XXXXXX
XXX.XX
XXXXXX
XX.X.X
XXXXXX
5
XXX.X
.X..X
XXX.X
..X..
..X..


Output


.X.
XOX
.X.
XX.XXO
XOXXOX
OXX.XX
XOOXXO
XX.X.X
OXXOXX
XOX.X
.X..X
XXO.O
..X..
..X..

Note

In the first test case, there are initially three 'X' consecutive in the second row and the second column. By changing the middle token to 'O' we make the grid a draw, and we only changed 1≤ ⌊ 5/3⌋ token.

In the second test case, we change only 9≤ ⌊ 32/3⌋ tokens, and there does not exist any three 'X' or 'O' consecutive in a row or column, so it is a draw.

In the third test case, we change only 3≤ ⌊ 12/3⌋ tokens, and the resulting grid is a draw.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In a dream Marco met an elderly man with a pair of black glasses. The man told him the key to immortality and then disappeared with the wind of time.

When he woke up, he only remembered that the key was a sequence of positive integers of some length n, but forgot the exact sequence. Let the elements of the sequence be a_1, a_2, ..., a_{n}. He remembered that he calculated gcd(a_{i}, a_{i} + 1, ..., a_{j}) for every 1 ≤ i ≤ j ≤ n and put it into a set S. gcd here means the greatest common divisor.

Note that even if a number is put into the set S twice or more, it only appears once in the set.

Now Marco gives you the set S and asks you to help him figure out the initial sequence. If there are many solutions, print any of them. It is also possible that there are no sequences that produce the set S, in this case print -1.


-----Input-----

The first line contains a single integer m (1 ≤ m ≤ 1000) — the size of the set S.

The second line contains m integers s_1, s_2, ..., s_{m} (1 ≤ s_{i} ≤ 10^6) — the elements of the set S. It's guaranteed that the elements of the set are given in strictly increasing order, that means s_1 < s_2 < ... < s_{m}.


-----Output-----

If there is no solution, print a single line containing -1.

Otherwise, in the first line print a single integer n denoting the length of the sequence, n should not exceed 4000.

In the second line print n integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^6) — the sequence.

We can show that if a solution exists, then there is a solution with n not exceeding 4000 and a_{i} not exceeding 10^6.

If there are multiple solutions, print any of them.


-----Examples-----
Input
4
2 4 6 12

Output
3
4 6 12
Input
2
2 3

Output
-1



-----Note-----

In the first example 2 = gcd(4, 6), the other elements from the set appear in the sequence, and we can show that there are no values different from 2, 4, 6 and 12 among gcd(a_{i}, a_{i} + 1, ..., a_{j}) for every 1 ≤ i ≤ j ≤ n.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Petya studies in a school and he adores Maths. His class has been studying arithmetic expressions. On the last class the teacher wrote three positive integers a, b, c on the blackboard. The task was to insert signs of operations '+' and '*', and probably brackets between the numbers so that the value of the resulting expression is as large as possible. Let's consider an example: assume that the teacher wrote numbers 1, 2 and 3 on the blackboard. Here are some ways of placing signs and brackets:  1+2*3=7  1*(2+3)=5  1*2*3=6  (1+2)*3=9 

Note that you can insert operation signs only between a and b, and between b and c, that is, you cannot swap integers. For instance, in the given sample you cannot get expression (1+3)*2.

It's easy to see that the maximum value that you can obtain is 9.

Your task is: given a, b and c print the maximum value that you can get.


-----Input-----

The input contains three integers a, b and c, each on a single line (1 ≤ a, b, c ≤ 10).


-----Output-----

Print the maximum value of the expression that you can obtain.


-----Examples-----
Input
1
2
3

Output
9

Input
2
10
3

Output
60

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Clear The Matrix

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You are given a matrix *f* with 4 rows and *n* columns. Each element of the matrix is either an asterisk (*) or a dot (.).

You may perform the following operation arbitrary number of times: choose a square submatrix of *f* with size *k*<=×<=*k* (where 1<=≤<=*k*<=≤<=4) and replace each element of the chosen submatrix with a dot. Choosing a submatrix of size *k*<=×<=*k* costs *a**k* coins.

What is the minimum number of coins you have to pay to replace all asterisks with dots?

Input Specification:
The first line contains one integer *n* (4<=≤<=*n*<=≤<=1000) — the number of columns in *f*.

The second line contains 4 integers *a*1, *a*2, *a*3, *a*4 (1<=≤<=*a**i*<=≤<=1000) — the cost to replace the square submatrix of size 1<=×<=1, 2<=×<=2, 3<=×<=3 or 4<=×<=4, respectively.

Then four lines follow, each containing *n* characters and denoting a row of matrix *f*. Each character is either a dot or an asterisk.

Output Specification:
Print one integer — the minimum number of coins to replace all asterisks with dots.

Demo Input:
['4\n1 10 8 20\n***.\n***.\n***.\n...*\n', '7\n2 1 8 2\n.***...\n.***..*\n.***...\n....*..\n', '4\n10 10 1 10\n***.\n*..*\n*..*\n.***\n']

Demo Output:
['9\n', '3\n', '2\n']

Note:
In the first example you can spend 8 coins to replace the submatrix 3 × 3 in the top-left corner, and 1 coin to replace the 1 × 1 submatrix in the bottom-right corner.

In the second example the best option is to replace the 4 × 4 submatrix containing columns 2 – 5, and the 2 × 2 submatrix consisting of rows 2 – 3 and columns 6 – 7.

In the third example you can select submatrix 3 × 3 in the top-left corner and then submatrix 3 × 3 consisting of rows 2 – 4 and columns 2 – 4.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Galois is one of the strongest chess players of Byteforces. He has even invented a new variant of chess, which he named «PawnChess».

This new game is played on a board consisting of 8 rows and 8 columns. At the beginning of every game some black and white pawns are placed on the board. The number of black pawns placed is not necessarily equal to the number of white pawns placed. 

Lets enumerate rows and columns with integers from 1 to 8. Rows are numbered from top to bottom, while columns are numbered from left to right. Now we denote as (*r*,<=*c*) the cell located at the row *r* and at the column *c*.

There are always two players A and B playing the game. Player A plays with white pawns, while player B plays with black ones. The goal of player A is to put any of his pawns to the row 1, while player B tries to put any of his pawns to the row 8. As soon as any of the players completes his goal the game finishes immediately and the succeeded player is declared a winner.

Player A moves first and then they alternate turns. On his move player A must choose exactly one white pawn and move it one step upward and player B (at his turn) must choose exactly one black pawn and move it one step down. Any move is possible only if the targeted cell is empty. It's guaranteed that for any scenario of the game there will always be at least one move available for any of the players.

Moving upward means that the pawn located in (*r*,<=*c*) will go to the cell (*r*<=-<=1,<=*c*), while moving down means the pawn located in (*r*,<=*c*) will go to the cell (*r*<=+<=1,<=*c*). Again, the corresponding cell must be empty, i.e. not occupied by any other pawn of any color.

Given the initial disposition of the board, determine who wins the game if both players play optimally. Note that there will always be a winner due to the restriction that for any game scenario both players will have some moves available.

Input Specification:
The input consists of the board description given in eight lines, each line contains eight characters. Character 'B' is used to denote a black pawn, and character 'W' represents a white pawn. Empty cell is marked with '.'. 

It's guaranteed that there will not be white pawns on the first row neither black pawns on the last row.

Output Specification:
Print 'A' if player A wins the game on the given board, and 'B' if player B will claim the victory. Again, it's guaranteed that there will always be a winner on the given board.

Demo Input:
['........\n........\n.B....B.\n....W...\n........\n..W.....\n........\n........\n', '..B.....\n..W.....\n......B.\n........\n.....W..\n......B.\n........\n........\n']

Demo Output:
['A\n', 'B\n']

Note:
In the first sample player A is able to complete his goal in 3 steps by always moving a pawn initially located at (4, 5). Player B needs at least 5 steps for any of his pawns to reach the row 8. Hence, player A will be the winner.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are N integers, A_1, A_2, ..., A_N, written on the blackboard.
You will choose one of them and replace it with an integer of your choice between 1 and 10^9 (inclusive), possibly the same as the integer originally written.
Find the maximum possible greatest common divisor of the N integers on the blackboard after your move.

-----Constraints-----
 - All values in input are integers.
 - 2 \leq N \leq 10^5
 - 1 \leq A_i \leq 10^9

-----Output-----
Input is given from Standard Input in the following format:
N
A_1 A_2 ... A_N

-----Output-----
Print the maximum possible greatest common divisor of the N integers on the blackboard after your move.

-----Sample Input-----
3
7 6 8

-----Sample Output-----
2

If we replace 7 with 4, the greatest common divisor of the three integers on the blackboard will be 2, which is the maximum possible value.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a non-empty array of integers, return the third maximum number in this array. If it does not exist, return the maximum number. The time complexity must be in O(n).

Example 1:

Input: [3, 2, 1]

Output: 1

Explanation: The third maximum is 1.



Example 2:

Input: [1, 2]

Output: 2

Explanation: The third maximum does not exist, so the maximum (2) is returned instead.



Example 3:

Input: [2, 2, 3, 1]

Output: 1

Explanation: Note that the third maximum here means the third maximum distinct number.
Both numbers with value 2 are both considered as second maximum.

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