vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: Mancala

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Mancala is a game famous in the Middle East. It is played on a board that consists of 14 holes. 

Initially, each hole has $a_i$ stones. When a player makes a move, he chooses a hole which contains a positive number of stones. He takes all the stones inside it and then redistributes these stones one by one in the next holes in a counter-clockwise direction.

Note that the counter-clockwise order means if the player takes the stones from hole $i$, he will put one stone in the $(i+1)$-th hole, then in the $(i+2)$-th, etc. If he puts a stone in the $14$-th hole, the next one will be put in the first hole.

After the move, the player collects all the stones from holes that contain even number of stones. The number of stones collected by player is the score, according to Resli.

Resli is a famous Mancala player. He wants to know the maximum score he can obtain after one move.

Input Specification:
The only line contains 14 integers $a_1, a_2, \ldots, a_{14}$ ($0 \leq a_i \leq 10^9$) — the number of stones in each hole.

It is guaranteed that for any $i$ ($1\leq i \leq 14$) $a_i$ is either zero or odd, and there is at least one stone in the board.

Output Specification:
Output one integer, the maximum possible score after one move.

Demo Input:
['0 1 1 0 0 0 0 0 0 7 0 0 0 0\n', '5 1 1 1 1 0 0 0 0 0 0 0 0 0\n']

Demo Output:
['4\n', '8\n']

Note:
In the first test case the board after the move from the hole with $7$ stones will look like 1 2 2 0 0 0 0 0 0 0 1 1 1 1. Then the player collects the even numbers and ends up with a score equal to $4$.

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

Given a string, add the fewest number of characters possible from the front or back to make it a palindrome.

## Example

For the input `cdcab`, the output should be `bacdcab`

## Input/Output

Input is a string consisting of lowercase latin letters with length 3 <= str.length <= 10

The output is a palindrome string satisfying the task.

For s = `ab` either solution (`aba` or `bab`) will be accepted.

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

You were solving a flow problem that is typical of graph algorithms.
The graph given in the problem is $ N $ vertices and $ M $ edges, with edges from $ x_i $ vertices to $ y_i $ vertices with capacity $ z_i $ and cost $ d_i $. However, AOR Ika played a trick on the input case. As a result, the order of $ x_i, y_i, z_i $ was shuffled, making it impossible to distinguish between vertex information and capacity information.

So you gave up trying to find the flow between $ s-t $ and decided to find the shortest distance between $ s-t $. You decide to use two of the input cases $ a_i, b_i, c_i $ with shuffled order of $ x_i, y_i, z_i $ as vertex information and edge the cost $ d_i $. In other words, the cost $ d_i $ is placed on one of the three candidates from $ a_i $ to $ b_i $, $ a_i $ to $ c_i $, and $ b_i $ to $ c_i $.

Find the minimum value of "the shortest distance from s to t" among the possible graphs.



input

$ N \ M \ s \ t $
$ a_1 \ b_1 \ c_1 \ d_1 $
$ \ vdots $
$ a_M \ b_M \ c_M \ d_M $

output

Output the minimum value of "the shortest distance from $ s $ to $ t $" in one line among the possible graphs. Also, output a line break at the end.

Example

Input

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


Output

7

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Jon wants to go in birthday party of Arya. But he is busy in finding solution of crazy equations, so he wants your help to solve this problem. Jon has four integers a, b, c, d now he wants to calculate how many distinct set of x, y, z, w are present such that  a + b - x  == a + c - y == c + d - z == b + d - w
NOTE :  1<= x, y, z, w<=n   where n is a given integer.
Two set of x, y, z, w will be different if atleast one value will be different.
Example 1:
Input: n = 5, a = 1, b = 2, c = 2, d = 2
Output: 4
Explanation: Sets of x, y, z, w can be
             (1, 1, 2, 2)
             (2, 2, 3, 3)
             (3, 3, 4, 4)
             (4, 4, 5, 5).
Example 2:
Input: n = 5, a = 1, b = 2, c = 2, d = 1
Output: 5
Explanation: same explanation as previous one.
Your Task:  
You dont need to read input or print anything. Complete the function distinctValues() which takes n, a, b, c and d as input parameter and returns the total number of distinct set of x, y, z, w are present. 
Expected Time Complexity: O(n)
Expected Auxiliary Space: O(1)
Constraints:
1 <= n <= 10^{6}
1 <= a, b, c, d <= n

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A cubeword is a special type of a crossword. When building a cubeword, you start by choosing a positive integer a: the side length of the cube. Then, you build a big cube consisting of a × a × a unit cubes. This big cube has 12 edges. Then, you discard all unit cubes that do not touch the edges of the big cube. The figure below shows the object you will get for a=6.

<image>

Finally, you assign a letter to each of the unit cubes in the object. You must get a meaningful word along each edge of the big cube. Each edge can be read in either direction, and it is sufficient if one of the two directions of reading gives a meaningful word.

The figure below shows the object for a=6 in which some unit cubes already have assigned letters. You can already read the words 'SUBMIT', 'ACCEPT' and 'TURING' along three edges of the big cube.

<image>

You are given a list of valid words. Each word from the wordlist may appear on arbitrarily many edges of a valid cubeword. Find and report the number of different cubewords that can be constructed, modulo 998,244,353.

If one cubeword can be obtained from another by rotation or mirroring, they are considered distinct.

Input

The first line contains a single integer n (1 ≤ n ≤ 100,000) – the number of words.

Then, n lines follow. Each of these lines contains one word that can appear on the edges of the big cube. The length of each word is between 3 and 10, inclusive.

It is guaranteed that all words are different.

Output

Output a single integer, the number of distinct cubewords for the given list of valid words modulo 998,244,353.

Scoring

Subtask 1 (21 points): the words consist only of letters 'a' - 'f' (lowercase)

Subtask 2 (29 points): the words consist only of letters 'a' - 'p' (lowercase)

Subtask 3 (34 points): the words consist of letters 'a' - 'p' (lowercase) and 'A' - 'P' (uppercase)

Subtask 4 (16 points): the words consist of letters 'a' - 'z' (lowercase), 'A' - 'Z' (uppercase) and digits '0' - '9'

Examples

Input


1
radar


Output


1


Input


1
robot


Output


2


Input


2
FLOW
WOLF


Output


2


Input


2
baobab
bob


Output


4097


Input


3
TURING
SUBMIT
ACCEPT


Output


162


Input


3
MAN1LA
MAN6OS
AN4NAS


Output


114

Note

In the first sample, the only possibility is for the word "radar" to be on each edge of the cube.

In the second sample, there are two cubes, which are just rotations of each other – the word "robot" is on every edge, and the difference between the two cubes is whether the lower left front corner contains 'r' or 't'.

The third sample is similar to the second one. The fact that we can read the word on each edge in both directions does not affect the answer.

In the fourth sample, there is one cube with the word "bob" on each edge. There are also 2^{12} = 4096 cubes with the word "baobab" on each edge. (For each of the 12 edges, we have two possible directions in which the word "baobab" can appear.)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
T.I. Financial Group, a world-famous group of finance companies, has decided to hold an evil gambling game in which insolvent debtors compete for special treatment of exemption from their debts.

In this game, each debtor starts from one cell on the stage called the Deadly Ring. The Deadly Ring consists of N cells and each cell is colored black or red. Each cell is connected to exactly two other adjacent cells and all the cells form a ring. At the start of the game, each debtor chooses which cell to start. Then he rolls a die and moves on the ring in clockwise order by cells as many as the number of spots shown on the upside of the die. This step is called a round, and each debtor repeats a round T times. A debtor will be exempted from his debt if he is standing on a red cell after he finishes all the rounds. On the other hand, if he finishes the game at a black cell, he will be sent somewhere else and forced to devote his entire life to hard labor.

You have happened to take part in this game. As you are allowed to choose the starting cell, you want to start from a cell that maximizes the probability of finishing the game at a red cell. Fortunately you can bring a laptop PC to the game stage, so you have decided to write a program that calculates the maximum winning probability.



Input

The input consists of multiple datasets.

Each dataset consists of two lines. The first line contains two integers N (1 ≤ N ≤ 2000) and T (1 ≤ T ≤ 2000) in this order, delimited with a single space. The second line contains a string of N characters that consists of characters ‘R’ and ‘B’, which indicate red and black respectively. This string represents the colors of the cells in clockwise order.

The input is terminated by a line with two zeros. This is not part of any datasets and should not be processed.

Output

For each dataset, print the maximum probability of finishing the game at a red cell in one line. Your program may output an arbitrary number of digits after the decimal point, provided that the absolute error does not exceed 10-8.

Example

Input

6 1
RBRBRB
10 1
RBBBRBBBBB
10 2
RBBBRBBBBB
10 10
RBBBBBBBBB
0 0


Output

0.50000000
0.33333333
0.22222222
0.10025221

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vidur is very much interested in Job scheduling techniques being used for improving the performance of computing systems. This semester he has been working on developing some new methods to schedule jobs on a computer.
Today, he is testing job scheduling using Dequeues on his system. The jobs which need to be processed by CPU are stored in a Dequeue. Each job is assigned some priority value P. Every time scheduler selects a job from either end of the Dequeue.

Now to counter the problem of Aging, he uses a method different from the existing ones. If the scheduler has to select a job, the priority value of a job becomes P * a, where a is the age of that job. 

To analyse the data later, Vidur saves the sum of priorities of each job in a file. 

Now, the scheduler works like this. It selects the jobs in such a way that the sum of priorities of the jobs is maximized. 

Note:
Priorities are considered just when a job is processed.
The first job has age a = 1. Each job takes one unit of time to get processed. Thus, the age of second job would be a=2.

INPUT:
The first line of input contains N which represents the number of jobs to be processed.
Then N lines follow.
ith line contains the priority value of ith process.

OUTOUT:
Output the sum for each set of jobs in a single line.

Constraints:
1 < N ≤2000 
1 ≤ P[i] ≤ 2000

SAMPLE INPUT
4
1
2
1
4

SAMPLE OUTPUT
24

Explanation

The order in which jobs would be processed are 1,2,1,4. Then, Sum = 1x1 + 2x2 + 1x3 + 4x4.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array A of n positive numbers. The task is to find the first index in the array such that the sum of elements before it is equal to the sum of elements after it.
Note:  Array is 1-based indexed.
Example 1:
Input: 
n = 5 
A[] = {1,3,5,2,2} 
Output: 3 
Explanation: For second test case 
at position 3 elements before it 
(1+3) = elements after it (2+2). 
 
Example 2:
Input:
n = 1
A[] = {1}
Output: 1
Explanation:
Since its the only element hence
it is the only point.
Your Task:
The task is to complete the function equalSum() which takes the array and n as input parameters and returns the point. Return -1 if no such point exists. 
Expected Time Complexily: O(N)
Expected Space Complexily: O(1)
Constraints:
1 <= n <= 10^{6}
1 <= A[i] <= 10^{8}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The name of one small but proud corporation consists of n lowercase English letters. The Corporation has decided to try rebranding — an active marketing strategy, that includes a set of measures to change either the brand (both for the company and the goods it produces) or its components: the name, the logo, the slogan. They decided to start with the name.

For this purpose the corporation has consecutively hired m designers. Once a company hires the i-th designer, he immediately contributes to the creation of a new corporation name as follows: he takes the newest version of the name and replaces all the letters xi by yi, and all the letters yi by xi. This results in the new version. It is possible that some of these letters do no occur in the string. It may also happen that xi coincides with yi. The version of the name received after the work of the last designer becomes the new name of the corporation.

Manager Arkady has recently got a job in this company, but is already soaked in the spirit of teamwork and is very worried about the success of the rebranding. Naturally, he can't wait to find out what is the new name the Corporation will receive.

Satisfy Arkady's curiosity and tell him the final version of the name.

Input

The first line of the input contains two integers n and m (1 ≤ n, m ≤ 200 000) — the length of the initial name and the number of designers hired, respectively.

The second line consists of n lowercase English letters and represents the original name of the corporation.

Next m lines contain the descriptions of the designers' actions: the i-th of them contains two space-separated lowercase English letters xi and yi.

Output

Print the new name of the corporation.

Examples

Input

6 1
police
p m


Output

molice


Input

11 6
abacabadaba
a b
b c
a d
e g
f a
b b


Output

cdcbcdcfcdc

Note

In the second sample the name of the corporation consecutively changes as follows:

<image>

<image>

<image>

<image>

<image>

<image>

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

Time Limit: 5 seconds

Memory Limit: 256 megabytes

Problem Description:
The DNA sequence for every living creature in Berland can be represented as a non-empty line consisting of lowercase Latin letters. Berland scientists found out that all the creatures evolve by stages. During one stage exactly one symbol of the DNA line is replaced by exactly two other ones. At that overall there are *n* permissible substitutions. The substitution *a**i*-&gt;*b**i**c**i* means that any one symbol *a**i* can be replaced with two symbols *b**i**c**i*. Every substitution could happen an unlimited number of times.

They say that two creatures with DNA sequences *s*1 and *s*2 can have a common ancestor if there exists such a DNA sequence *s*3 that throughout evolution it can result in *s*1 and *s*2, perhaps after a different number of stages. Your task is to find out by the given *s*1 and *s*2 whether the creatures possessing such DNA sequences can have a common ancestor. If the answer is positive, you have to find the length of the shortest sequence of the common ancestor’s DNA.

Input Specification:
The first line contains a non-empty DNA sequence *s*1, the second line contains a non-empty DNA sequence *s*2. The lengths of these lines do not exceed 50, the lines contain only lowercase Latin letters. The third line contains an integer *n* (0<=≤<=*n*<=≤<=50) — the number of permissible substitutions. Then follow *n* lines each of which describes a substitution in the format *a**i*-&gt;*b**i**c**i*. The characters *a**i*, *b**i*, and *c**i* are lowercase Latin letters. Lines *s*1 and *s*2 can coincide, the list of substitutions can contain similar substitutions.

Output Specification:
If *s*1 and *s*2 cannot have a common ancestor, print -1. Otherwise print the length of the shortest sequence *s*3, from which *s*1 and *s*2 could have evolved.

Demo Input:
['ababa\naba\n2\nc-&gt;ba\nc-&gt;cc\n', 'ababa\naba\n7\nc-&gt;ba\nc-&gt;cc\ne-&gt;ab\nz-&gt;ea\nb-&gt;ba\nd-&gt;dd\nd-&gt;ab\n', 'ababa\naba\n1\nc-&gt;ba\n']

Demo Output:
['2\n', '1\n', '-1\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Now our heroes - Maga and Alex are working for Oil Company as developers. Recently they have faced a great problem. 

They couldn’t find the correct solution. Could you help them?

We are given r – radius of lower base and s – slant height. The figure can be cylinder or truncated cone. You have to find as largest volume as possible to carry oil respect to given information. The slant height is the shortest possible distance between the edges of two bases through surface of cone.

  

Input :

You are given 2 numbers. r– radius of lower base and s – slant height.

Output:

Largest Volume. Print 2 digits after floating point.

Constraints:

1 ≤ r, s ≤ 100

SAMPLE INPUT
1 1

SAMPLE OUTPUT
4.33

Explanation

In the sample test case, the answer is that it is truncated cone which the area of upper base is larger than the area of lower base. And then answer is simple 4.33.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
An Ironman Triathlon is one of a series of long-distance triathlon races organized by the World Triathlon Corporaion (WTC).
It consists of a 2.4-mile swim, a 112-mile bicycle ride and a marathon (26.2-mile) (run, raced in that order and without a break. It hurts... trust me.

Your task is to take a distance that an athlete is through the race, and return one of the following:

If the distance is zero, return `'Starting Line... Good Luck!'`.

If the athlete will be swimming, return an object with `'Swim'` as the key, and the remaining race distance as the value.

If the athlete will be riding their bike, return an object with `'Bike'` as the key, and the remaining race distance as the value.

If the athlete will be running, and has more than 10 miles to go, return an object with `'Run'` as the key, and the remaining race distance as the value.

If the athlete has 10 miles or less to go, return return an object with `'Run'` as the key, and `'Nearly there!'` as the value.

Finally, if the athlete has completed te distance, return `"You're done! Stop running!"`.

All distance should be calculated to two decimal places.

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$ integers numbered from $1$ to $n$.

Let's define the $k$-amazing number of the array as the minimum number that occurs in all of the subsegments of the array having length $k$ (recall that a subsegment of $a$ of length $k$ is a contiguous part of $a$ containing exactly $k$ elements). If there is no integer occuring in all subsegments of length $k$ for some value of $k$, then the $k$-amazing number is $-1$.

For each $k$ from $1$ to $n$ calculate the $k$-amazing number of the array $a$.


-----Input-----

The first line contains one integer $t$ ($1 \le t \le 1000$) — the number of test cases. Then $t$ test cases follow.

The first line of each test case contains one integer $n$ ($1 \le n \le 3 \cdot 10^5$) — the number of elements in the array. The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$) — the elements of the array. 

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


-----Output-----

For each test case print $n$ integers, where the $i$-th integer is equal to the $i$-amazing number of the array.


-----Example-----
Input
3
5
1 2 3 4 5
5
4 4 4 4 2
6
1 3 1 5 3 1

Output
-1 -1 3 2 1 
-1 4 4 4 2 
-1 -1 1 1 1 1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given n points on a plane. 

Please find the minimum sum of areas of two axis-aligned rectangles, such that each point is contained in at least one of these rectangles.

Note that the chosen rectangles can be degenerate. Rectangle contains all the points that lie inside it or on its boundary.

Input

The first line contains one integer t (1 ≤ t ≤ 2 ⋅ 10^5) — the number of test cases.

The first line of each test case contains a single integer n (1 ≤ n ≤ 2 ⋅ 10^5) — the number of points.

The following n lines contain the coordinates of the points x_i and y_i (0 ≤ x_i, y_i ≤ 10^9). It is guaranteed that the points are distinct.

It is guaranteed that the sum of values n over all test cases does not exceed 2⋅10^5.

Output

For each test case print one integer — the minimum sum of areas.

Example

Input


3
2
9 1
1 6
2
8 10
0 7
4
0 0
1 1
9 9
10 10


Output


0
0
2

Note

In the first two test cases the answer consists of 2 degenerate rectangles. In the third test case one of the possible answers consists of two rectangles 1 × 1 with bottom left corners (0,0) and (9,9).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a permutation p_1, p_2, …, p_n.

In one move you can swap two adjacent values.

You want to perform a minimum number of moves, such that in the end there will exist a subsegment 1,2,…, k, in other words in the end there should be an integer i, 1 ≤ i ≤ n-k+1 such that p_i = 1, p_{i+1} = 2, …, p_{i+k-1}=k.

Let f(k) be the minimum number of moves that you need to make a subsegment with values 1,2,…,k appear in the permutation.

You need to find f(1), f(2), …, f(n).

Input

The first line of input contains one integer n (1 ≤ n ≤ 200 000): the number of elements in the permutation.

The next line of input contains n integers p_1, p_2, …, p_n: given permutation (1 ≤ p_i ≤ n).

Output

Print n integers, the minimum number of moves that you need to make a subsegment with values 1,2,…,k appear in the permutation, for k=1, 2, …, n.

Examples

Input


5
5 4 3 2 1


Output


0 1 3 6 10 


Input


3
1 2 3


Output


0 0 0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Two Bags of Potatoes

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Valera had two bags of potatoes, the first of these bags contains *x* (*x*<=≥<=1) potatoes, and the second — *y* (*y*<=≥<=1) potatoes. Valera — very scattered boy, so the first bag of potatoes (it contains *x* potatoes) Valera lost. Valera remembers that the total amount of potatoes (*x*<=+<=*y*) in the two bags, firstly, was not gerater than *n*, and, secondly, was divisible by *k*.

Help Valera to determine how many potatoes could be in the first bag. Print all such possible numbers in ascending order.

Input Specification:
The first line of input contains three integers *y*, *k*, *n* (1<=≤<=*y*,<=*k*,<=*n*<=≤<=109;  <=≤<=105).

Output Specification:
Print the list of whitespace-separated integers — all possible values of *x* in ascending order. You should print each possible value of *x* exactly once.

If there are no such values of *x* print a single integer -1.

Demo Input:
['10 1 10\n', '10 6 40\n']

Demo Output:
['-1\n', '2 8 14 20 26 \n']

Note:
none

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