vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
This is the easy version of the problem. The difference is the constraint on the sum of lengths of strings and the number of test cases. You can make hacks only if you solve all versions of this task.

You are given a string $s$, consisting of lowercase English letters. Find the longest string, $t$, which satisfies the following conditions:   The length of $t$ does not exceed the length of $s$.  $t$ is a palindrome.  There exists two strings $a$ and $b$ (possibly empty), such that $t = a + b$ ( "$+$" represents concatenation), and $a$ is prefix of $s$ while $b$ is suffix of $s$. 


-----Input-----

The input consists of multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 1000$), the number of test cases. The next $t$ lines each describe a test case.

Each test case is a non-empty string $s$, consisting of lowercase English letters.

It is guaranteed that the sum of lengths of strings over all test cases does not exceed $5000$.


-----Output-----

For each test case, print the longest string which satisfies the conditions described above. If there exists multiple possible solutions, print any of them.


-----Example-----
Input
5
a
abcdfdcecba
abbaxyzyx
codeforces
acbba

Output
a
abcdfdcba
xyzyx
c
abba



-----Note-----

In the first test, the string $s = $"a" satisfies all conditions.

In the second test, the string "abcdfdcba" satisfies all conditions, because:  Its length is $9$, which does not exceed the length of the string $s$, which equals $11$.  It is a palindrome.  "abcdfdcba" $=$ "abcdfdc" $+$ "ba", and "abcdfdc" is a prefix of $s$ while "ba" is a suffix of $s$. 

It can be proven that there does not exist a longer string which satisfies the conditions.

In the fourth test, the string "c" is correct, because "c" $=$ "c" $+$ "" and $a$ or $b$ can be empty. The other possible solution for this test is "s".

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
While Grisha was celebrating New Year with Ded Moroz, Misha gifted Sasha a small rectangular pond of size n × m, divided into cells of size 1 × 1, inhabited by tiny evil fishes (no more than one fish per cell, otherwise they'll strife!).

The gift bundle also includes a square scoop of size r × r, designed for fishing. If the lower-left corner of the scoop-net is located at cell (x, y), all fishes inside the square (x, y)...(x + r - 1, y + r - 1) get caught. Note that the scoop-net should lie completely inside the pond when used.

Unfortunately, Sasha is not that skilled in fishing and hence throws the scoop randomly. In order to not frustrate Sasha, Misha decided to release k fishes into the empty pond in such a way that the expected value of the number of caught fishes is as high as possible. Help Misha! In other words, put k fishes in the pond into distinct cells in such a way that when the scoop-net is placed into a random position among (n - r + 1)·(m - r + 1) possible positions, the average number of caught fishes is as high as possible.


-----Input-----

The only line contains four integers n, m, r, k (1 ≤ n, m ≤ 10^5, 1 ≤ r ≤ min(n, m), 1 ≤ k ≤ min(n·m, 10^5)).


-----Output-----

Print a single number — the maximum possible expected number of caught fishes.

You answer is considered correct, is its absolute or relative error does not exceed 10^{ - 9}. Namely, let your answer be a, and the jury's answer be b. Your answer is considered correct, if $\frac{|a - b|}{\operatorname{max}(1,|b|)} \leq 10^{-9}$.


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

Output
2.0000000000

Input
12 17 9 40

Output
32.8333333333



-----Note-----

In the first example you can put the fishes in cells (2, 1), (2, 2), (2, 3). In this case, for any of four possible positions of the scoop-net (highlighted with light green), the number of fishes inside is equal to two, and so is the expected value. [Image]

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is an automatic door at the entrance of a factory. The door works in the following way:  when one or several people come to the door and it is closed, the door immediately opens automatically and all people immediately come inside,  when one or several people come to the door and it is open, all people immediately come inside,  opened door immediately closes in d seconds after its opening,  if the door is closing and one or several people are coming to the door at the same moment, then all of them will have enough time to enter and only after that the door will close. 

For example, if d = 3 and four people are coming at four different moments of time t_1 = 4, t_2 = 7, t_3 = 9 and t_4 = 13 then the door will open three times: at moments 4, 9 and 13. It will close at moments 7 and 12.

It is known that n employees will enter at moments a, 2·a, 3·a, ..., n·a (the value a is positive integer). Also m clients will enter at moments t_1, t_2, ..., t_{m}.

Write program to find the number of times the automatic door will open. Assume that the door is initially closed.


-----Input-----

The first line contains four integers n, m, a and d (1 ≤ n, a ≤ 10^9, 1 ≤ m ≤ 10^5, 1 ≤ d ≤ 10^18) — the number of the employees, the number of the clients, the moment of time when the first employee will come and the period of time in which the door closes.

The second line contains integer sequence t_1, t_2, ..., t_{m} (1 ≤ t_{i} ≤ 10^18) — moments of time when clients will come. The values t_{i} are given in non-decreasing order.


-----Output-----

Print the number of times the door will open.


-----Examples-----
Input
1 1 3 4
7

Output
1

Input
4 3 4 2
7 9 11

Output
4



-----Note-----

In the first example the only employee will come at moment 3. At this moment the door will open and will stay open until the moment 7. At the same moment of time the client will come, so at first he will enter and only after it the door will close. Thus the door will open one time.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is an evil creature in a square on N-by-M grid (2 \leq N, M \leq 100), and you want to kill it using a laser generator located in a different square. Since the location and direction of the laser generator are fixed, you may need to use several mirrors to reflect laser beams. There are some obstacles on the grid and you have a limited number of mirrors. Please find out whether it is possible to kill the creature, and if possible, find the minimum number of mirrors.

There are two types of single-sided mirrors; type P mirrors can be placed at the angle of 45 or 225 degrees from east-west direction, and type Q mirrors can be placed with at the angle of 135 or 315 degrees. For example, four mirrors are located properly, laser go through like the following.

<image>

Note that mirrors are single-sided, and thus back side (the side with cross in the above picture) is not reflective. You have A type P mirrors, and also A type Q mirrors (0 \leq A \leq 10). Although you cannot put mirrors onto the squares with the creature or the laser generator, laser beam can pass through the square. Evil creature is killed if the laser reaches the square it is in.



Input

Each test case consists of several lines.

The first line contains three integers, N, M, and A. Each of the following N lines contains M characters, and represents the grid information. '#', '.', 'S', 'G' indicates obstacle, empty square, the location of the laser generator, and the location of the evil creature, respectively. The first line shows the information in northernmost squares and the last line shows the information in southernmost squares. You can assume that there is exactly one laser generator and exactly one creature, and the laser generator emits laser beam always toward the south.

Output

Output the minimum number of mirrors used if you can kill creature, or -1 otherwise.

Examples

Input

3 3 2
S#.
...
.#G


Output

2


Input

3 3 1
S#.
...
.#G


Output

-1


Input

3 3 1
S#G
...
.#.


Output

2


Input

4 3 2
S..
...
..#
.#G


Output

-1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Slavko is learning about different numeral systems. Slavko is not the brightest when it comes to math, so he is starting out converting binary numerals to octal. The algorithm Slavko uses is this:
 - Pad the binary numeral with zeros on the left until the number of digits is divisible by three.
 - Group adjacent binary digits into groups of $3$ digits.
 - Replace each group of binary digits with the corresponding octal digit (as in Table 1).

000

0

001

1

010

2

011

3

100

4

101

5

110

6

111

7Table 1: Binary to octal 

Write a program that converts a binary numeral to octal so that Slavko can verify his results.

-----Input-----
The input contains a binary numeral. The number of digits will be less than $100$, and the first digit will be $1$.

-----Output-----
Output the number in octal.

-----Examples-----
Sample Input:
1010
Sample Output:
12

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Demiurges Shambambukli and Mazukta love to watch the games of ordinary people. Today, they noticed two men who play the following game.

There is a rooted tree on *n* nodes, *m* of which are leaves (a leaf is a nodes that does not have any children), edges of the tree are directed from parent to children. In the leaves of the tree integers from 1 to *m* are placed in such a way that each number appears exactly in one leaf.

Initially, the root of the tree contains a piece. Two players move this piece in turns, during a move a player moves the piece from its current nodes to one of its children; if the player can not make a move, the game ends immediately. The result of the game is the number placed in the leaf where a piece has completed its movement. The player who makes the first move tries to maximize the result of the game and the second player, on the contrary, tries to minimize the result. We can assume that both players move optimally well.

Demiurges are omnipotent, so before the game they can arbitrarily rearrange the numbers placed in the leaves. Shambambukli wants to rearrange numbers so that the result of the game when both players play optimally well is as large as possible, and Mazukta wants the result to be as small as possible. What will be the outcome of the game, if the numbers are rearranged by Shambambukli, and what will it be if the numbers are rearranged by Mazukta? Of course, the Demiurges choose the best possible option of arranging numbers.

Input Specification:
The first line contains a single integer *n* — the number of nodes in the tree (1<=≤<=*n*<=≤<=2·105).

Each of the next *n*<=-<=1 lines contains two integers *u**i* and *v**i* (1<=≤<=*u**i*,<=*v**i*<=≤<=*n*) — the ends of the edge of the tree; the edge leads from node *u**i* to node *v**i*. It is guaranteed that the described graph is a rooted tree, and the root is the node 1.

Output Specification:
Print two space-separated integers — the maximum possible and the minimum possible result of the game.

Demo Input:
['5\n1 2\n1 3\n2 4\n2 5\n', '6\n1 2\n1 3\n3 4\n1 5\n5 6\n']

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

Note:
Consider the first sample. The tree contains three leaves: 3, 4 and 5. If we put the maximum number 3 at node 3, then the first player moves there and the result will be 3. On the other hand, it is easy to see that for any rearrangement the first player can guarantee the result of at least 2.

In the second sample no matter what the arragment is the first player can go along the path that ends with a leaf with number 3.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Gennady and Artem are discussing solutions of different problems.
Gennady told Artem about a number theory problem he solved the day before.
One of steps to solve the problem was to calculate the least common multiple (LCM) of all integers from 1 to n, inclusive.
That problem inspired Gennady to come up with another problem about LCM's.

Given n, find the greatest m that m ≤ n and:
$LCM(1, 2, \ldots, n) = LCM(m, m + 1, \ldots, n)$

We have no doubt Artem will solve the problem, but will you?

You can find the definition of LCM here.

Input format
The only line of the input contains one integer n.

Output format
Print the greatest integer m satisfying the given conditions.

Constraints

1 ≤ n ≤ 10^{15}

SAMPLE INPUT
5

SAMPLE OUTPUT
3

Explanation

LCM(1, 2, 3, 4, 5) = 60
LCM(2, 3, 4, 5) = 60
LCM(3, 4, 5) = 60
LCM(4, 5) = 20

m = 3 is the greatest integer for which LCM(m, m+1, \ldots, 5) = LCM(1, 2, 3, 4, 5) = 60.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Alice and Bob are playing a game. There are $n$ cells in a row. Initially each cell is either red or blue. Alice goes first.

On each turn, Alice chooses two neighbouring cells which contain at least one red cell, and paints that two cells white. Then, Bob chooses two neighbouring cells which contain at least one blue cell, and paints that two cells white. The player who cannot make a move loses.

Find the winner if both Alice and Bob play optimally.

Note that a chosen cell can be white, as long as the other cell satisfies the constraints.


-----Input-----

The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. Description of test cases follows.

For each test case, the first line contains an integer $n$ ($2 \leq n \leq 5 \cdot 10^5$) — the number of cells.

The second line contains a string $s$ of length $n$ — the initial state of the cells. The $i$-th cell is red if $s_i = $ R, blue if $s_i = $ B.

It is guaranteed that the sum of $n$ over all test cases does not exceed $5 \cdot 10^5$.


-----Output-----

For each test case, output the name of the winner on a separate line.


-----Examples-----

Input
8
3
BRB
5
RRBBB
6
RBRBRB
8
BBRRBRRB
6
BRRBRB
12
RBRBRBRBRRBB
12
RBRBRBRBBBRR
4
RBBR
Output
Bob
Bob
Alice
Alice
Alice
Alice
Bob
Bob


-----Note-----

In the notes, the cell numbers increase from left to right.

In the first testcase for Alice, she has two choices: paint the first and the second cells, or paint the second and the third cells. No matter what choice Alice makes, there will be exactly one blue cell after Alice's move. Bob just needs to paint the blue cell and its neighbour, then every cell will be white and Alice can't make a move. So Bob is the winner.

In the second testcase no matter what Alice chooses, Bob can choose to paint the fourth and fifth cells in $2$ turns.

In the third testcase at first, Alice paints the third and the fourth cells. It doesn't matter if Bob paints the first and the second cells or the fifth and sixth cells, as Alice can paint the other two cells.

In the fourth testcase at first, Alice paints the second and the third cells. If Bob paints the fifth and the sixth cells or the fourth and the fifth cells, then Alice paints the seventh and the eighth cells. If Bob paints the seventh and the eighth cells, then Alice paints the fifth and the sixth cells.

In the fifth Alice chooses the middle two cells at first, then Bob obviously has only two options, whichever variant he chooses, Alice can choose the other one and win.

In the eighth no matter what Alice chooses, Bob can choose the other two symmetrical cells.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are n reindeer at the North Pole, all battling for the highest spot on the "Top Reindeer" leaderboard on the front page of CodeNorses (a popular competitive reindeer gaming website). Interestingly, the "Top Reindeer" title is just a measure of upvotes and has nothing to do with their skill level in the reindeer games, but they still give it the utmost importance.

Currently, the i-th reindeer has a score of a_i. You would like to influence the leaderboard with some operations. In an operation, you can choose a reindeer, and either increase or decrease his score by 1 unit. Negative scores are allowed.

You have m requirements for the resulting scores. Each requirement is given by an ordered pair (u, v), meaning that after all operations, the score of reindeer u must be less than or equal to the score of reindeer v.

Your task is to perform the minimum number of operations so that all requirements will be satisfied.

Input

The first line contains two integers n and m (2≤ n≤ 1000; 1≤ m≤ 1000) — the number of reindeer and requirements, respectively.

The second line contains n integers a_1,…, a_n (1≤ a_i≤ 10^9), where a_i is the current score of reindeer i.

The next m lines describe the requirements.

The i-th of these lines contains two integers u_i and v_i (1≤ u_i, v_i≤ n; u_i≠ v_i) — the two reindeer of the i-th requirement.

Output

Print n integers b_1,…, b_n (-10^{15}≤ b_i≤ 10^{15}), where b_i is the score of the i-th reindeer after all operations.

If there are multiple solutions achieving the minimum number of operations, you may output any.

We can prove that there is always an optimal solution such that |b_i|≤ 10^{15} for all i.

Examples

Input


7 6
3 1 4 9 2 5 6
1 2
2 3
3 4
4 5
5 6
6 7


Output


1 1 4 4 4 5 6 


Input


4 6
6 5 8 2
3 1
4 1
3 2
1 2
2 3
3 1


Output


6 6 6 2 


Input


10 18
214 204 195 182 180 176 176 172 169 167
1 2
3 2
4 2
5 2
6 2
7 2
8 2
9 2
10 2
6 1
6 2
6 3
6 4
6 5
6 7
6 8
6 9
6 10


Output


204 204 195 182 180 167 176 172 169 167

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
AquaMoon has three integer arrays a, b, c of length n, where 1 ≤ a_i, b_i, c_i ≤ n for all i.

In order to accelerate her potato farming, she organizes her farm in a manner based on these three arrays. She is now going to complete m operations to count how many potatoes she can get. Each operation will have one of the two types:

  1. AquaMoon reorganizes their farm and makes the k-th element of the array a equal to x. In other words, perform the assignment a_k := x. 
  2. Given a positive integer r, AquaMoon receives a potato for each triplet (i,j,k), such that 1≤ i<j<k≤ r, and b_{a_i}=a_j=c_{a_k}. Count the number of such triplets. 



As AquaMoon is busy finding the library, help her complete all of their operations.

Input

The first line contains two integers n, m (1≤ n≤ 2⋅10^5, 1≤ m≤ 5⋅10^4).

The second line contains n integers a_1, a_2, ...,a_n (1≤ a_i≤ n).

The third line contains n integers b_1, b_2, ...,b_n (1≤ b_i≤ n).

The fourth line contains n integers c_1, c_2, ...,c_n (1≤ c_i≤ n).

The next m lines describe operations, the i-th line describes the i-th operation in one of these two formats:

  * "1\ k\ x" (1≤ k,x≤ n), representing an operation of the first type. 
  * "2\ r" (1≤ r≤ n), representing an operation of the second type. 



It is guaranteed that there is at least one operation of the second type.

Output

For each operation of the second type print the answer.

Example

Input


5 4
1 2 3 4 5
2 3 4 5 1
5 1 2 3 4
2 5
1 2 3
2 4
2 5


Output


3
0
2

Note

For the first operation, the triplets are:

  * i=1, j=2, k=3 
  * i=2, j=3, k=4 
  * i=3, j=4, k=5 



There is no satisfying triplet for the third operation.

For the fourth operation, the triplets are:

  * i=2, j=4, k=5 
  * i=3, j=4, k=5 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In Summer Informatics School, if a student doesn't behave well, teachers make a hole in his badge. And today one of the teachers caught a group of $n$ students doing yet another trick. 

Let's assume that all these students are numbered from $1$ to $n$. The teacher came to student $a$ and put a hole in his badge. The student, however, claimed that the main culprit is some other student $p_a$.

After that, the teacher came to student $p_a$ and made a hole in his badge as well. The student in reply said that the main culprit was student $p_{p_a}$.

This process went on for a while, but, since the number of students was finite, eventually the teacher came to the student, who already had a hole in his badge.

After that, the teacher put a second hole in the student's badge and decided that he is done with this process, and went to the sauna.

You don't know the first student who was caught by the teacher. However, you know all the numbers $p_i$. Your task is to find out for every student $a$, who would be the student with two holes in the badge if the first caught student was $a$.


-----Input-----

The first line of the input contains the only integer $n$ ($1 \le n \le 1000$) — the number of the naughty students.

The second line contains $n$ integers $p_1$, ..., $p_n$ ($1 \le p_i \le n$), where $p_i$ indicates the student who was reported to the teacher by student $i$.


-----Output-----

For every student $a$ from $1$ to $n$ print which student would receive two holes in the badge, if $a$ was the first student caught by the teacher.


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

Output
2 2 3 

Input
3
1 2 3

Output
1 2 3 



-----Note-----

The picture corresponds to the first example test case.

 $8$ 

When $a = 1$, the teacher comes to students $1$, $2$, $3$, $2$, in this order, and the student $2$ is the one who receives a second hole in his badge.

When $a = 2$, the teacher comes to students $2$, $3$, $2$, and the student $2$ gets a second hole in his badge. When $a = 3$, the teacher will visit students $3$, $2$, $3$ with student $3$ getting a second hole in his badge.

For the second example test case it's clear that no matter with whom the teacher starts, that student would be the one who gets the second hole in his badge.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a text consisting of $n$ space-separated words. There is exactly one space character between any pair of adjacent words. There are no spaces before the first word and no spaces after the last word. The length of text is the number of letters and spaces in it. $w_i$ is the $i$-th word of text. All words consist only of lowercase Latin letters.

Let's denote a segment of words $w[i..j]$ as a sequence of words $w_i, w_{i + 1}, \dots, w_j$. Two segments of words $w[i_1 .. j_1]$ and $w[i_2 .. j_2]$ are considered equal if $j_1 - i_1 = j_2 - i_2$, $j_1 \ge i_1$, $j_2 \ge i_2$, and for every $t \in [0, j_1 - i_1]$ $w_{i_1 + t} = w_{i_2 + t}$. For example, for the text "to be or not to be" the segments $w[1..2]$ and $w[5..6]$ are equal, they correspond to the words "to be".

An abbreviation is a replacement of some segments of words with their first uppercase letters. In order to perform an abbreviation, you have to choose at least two non-intersecting equal segments of words, and replace each chosen segment with the string consisting of first letters of the words in the segment (written in uppercase). For example, for the text "a ab a a b ab a a b c" you can replace segments of words $w[2..4]$ and $w[6..8]$ with an abbreviation "AAA" and obtain the text "a AAA b AAA b c", or you can replace segments of words $w[2..5]$ and $w[6..9]$ with an abbreviation "AAAB" and obtain the text "a AAAB AAAB c".

What is the minimum length of the text after at most one abbreviation?


-----Input-----

The first line of the input contains one integer $n$ ($1 \le n \le 300$) — the number of words in the text.

The next line contains $n$ space-separated words of the text $w_1, w_2, \dots, w_n$. Each word consists only of lowercase Latin letters.

It is guaranteed that the length of text does not exceed $10^5$.


-----Output-----

Print one integer — the minimum length of the text after at most one abbreviation.


-----Examples-----
Input
6
to be or not to be

Output
12

Input
10
a ab a a b ab a a b c

Output
13

Input
6
aa bb aa aa bb bb

Output
11



-----Note-----

In the first example you can obtain the text "TB or not TB".

In the second example you can obtain the text "a AAAB AAAB c".

In the third example you can obtain the text "AB aa AB bb".

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