vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Let's play a puzzle using eight cubes placed on a 3 × 3 board leaving one empty square.

Faces of cubes are painted with three colors. As a puzzle step, you can roll one of the cubes to the adjacent empty square. Your goal is to make the specified color pattern visible from above by a number of such steps.

The rules of this puzzle are as follows.

1. Coloring of Cubes: All the cubes are colored in the same way as shown in Figure 3. The opposite faces have the same color.

<image>

Figure 3: Coloring of a cube



2. Initial Board State: Eight cubes are placed on the 3 × 3 board leaving one empty square. All the cubes have the same orientation as shown in Figure 4. As shown in the figure, squares on the board are given x and y coordinates, (1, 1), (1, 2), .. ., and (3, 3). The position of the initially empty square may vary.

<image>

Figure 4: Initial board state



3. Rolling Cubes: At each step, we can choose one of the cubes adjacent to the empty square and roll it into the empty square, leaving the original position empty. Figure 5 shows an example.

<image>

Figure 5: Rolling a cube



4. Goal: The goal of this puzzle is to arrange the cubes so that their top faces form the specified color pattern by a number of cube rolling steps described above.



Your task is to write a program that finds the minimum number of steps required to make the specified color pattern from the given initial state.



Input

The input is a sequence of datasets. The end of the input is indicated by a line containing two zeros separated by a space. The number of datasets is less than 16. Each dataset is formatted as follows.


x y
F11 F21 F31
F12 F22 F32
F13 F23 F33


The first line contains two integers x and y separated by a space, indicating the position (x, y) of the initially empty square. The values of x and y are 1, 2, or 3.

The following three lines specify the color pattern to make. Each line contains three characters F1j, F2j, and F3j, separated by a space. Character Fij indicates the top color of the cube, if any, at position (i, j) as follows:


B: Blue
W: White
R: Red
E: the square is Empty.


There is exactly one 'E' character in each dataset.

Output

For each dataset, output the minimum number of steps to achieve the goal, when the goal can be reached within 30 steps. Otherwise, output "-1" for the dataset.

Example

Input

1 2
W W W
E W W
W W W
2 1
R B W
R W W
E W W
3 3
W B W
B R E
R B R
3 3
B W R
B W R
B E R
2 1
B B B
B R B
B R E
1 1
R R R
W W W
R R E
2 1
R R R
B W B
R R E
3 2
R R R
W E W
R R R
0 0


Output

0
3
13
23
29
30
-1
-1

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

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
There is a card game called "Durak", which means "Fool" in Russian. The game is quite popular in the countries that used to form USSR. The problem does not state all the game's rules explicitly — you can find them later yourselves if you want.

To play durak you need a pack of 36 cards. Each card has a suit ("S", "H", "D" and "C") and a rank (in the increasing order "6", "7", "8", "9", "T", "J", "Q", "K" and "A"). At the beginning of the game one suit is arbitrarily chosen as trump. 

The players move like that: one player puts one or several of his cards on the table and the other one should beat each of them with his cards.

A card beats another one if both cards have similar suits and the first card has a higher rank then the second one. Besides, a trump card can beat any non-trump card whatever the cards’ ranks are. In all other cases you can not beat the second card with the first one.

You are given the trump suit and two different cards. Determine whether the first one beats the second one or not.

Input Specification:
The first line contains the tramp suit. It is "S", "H", "D" or "C".

The second line contains the description of the two different cards. Each card is described by one word consisting of two symbols. The first symbol stands for the rank ("6", "7", "8", "9", "T", "J", "Q", "K" and "A"), and the second one stands for the suit ("S", "H", "D" and "C").

Output Specification:
Print "YES" (without the quotes) if the first cards beats the second one. Otherwise, print "NO" (also without the quotes).

Demo Input:
['H\nQH 9S\n', 'S\n8D 6D\n', 'C\n7H AS\n']

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

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vasya wants to buy himself a nice new car. Unfortunately, he lacks some money. Currently he has exactly 0 burles.

However, the local bank has $n$ credit offers. Each offer can be described with three numbers $a_i$, $b_i$ and $k_i$. Offers are numbered from $1$ to $n$. If Vasya takes the $i$-th offer, then the bank gives him $a_i$ burles at the beginning of the month and then Vasya pays bank $b_i$ burles at the end of each month for the next $k_i$ months (including the month he activated the offer). Vasya can take the offers any order he wants.

Each month Vasya can take no more than one credit offer. Also each credit offer can not be used more than once. Several credits can be active at the same time. It implies that Vasya pays bank the sum of $b_i$ over all the $i$ of active credits at the end of each month.

Vasya wants to buy a car in the middle of some month. He just takes all the money he currently has and buys the car of that exact price.

Vasya don't really care what he'll have to pay the bank back after he buys a car. He just goes out of the country on his car so that the bank can't find him anymore.

What is the maximum price that car can have?


-----Input-----

The first line contains one integer $n$ ($1 \le n \le 500$) — the number of credit offers.

Each of the next $n$ lines contains three integers $a_i$, $b_i$ and $k_i$ ($1 \le a_i, b_i, k_i \le 10^9$).


-----Output-----

Print one integer — the maximum price of the car.


-----Examples-----
Input
4
10 9 2
20 33 1
30 115 1
5 3 2

Output
32

Input
3
40 1 2
1000 1100 5
300 2 1

Output
1337



-----Note-----

In the first example, the following sequence of offers taken is optimal: 4 $\rightarrow$ 3.

The amount of burles Vasya has changes the following way: 5 $\rightarrow$ 32 $\rightarrow$ -86 $\rightarrow$ .... He takes the money he has in the middle of the second month (32 burles) and buys the car.

The negative amount of money means that Vasya has to pay the bank that amount of burles.

In the second example, the following sequence of offers taken is optimal: 3 $\rightarrow$ 1 $\rightarrow$ 2.

The amount of burles Vasya has changes the following way: 0 $\rightarrow$ 300 $\rightarrow$ 338 $\rightarrow$ 1337 $\rightarrow$ 236 $\rightarrow$ -866 $\rightarrow$ ....

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an integer n and a permutation of numbers 1, 2 ... , n-1, n write a program to print the permutation that lexicographically precedes the given input permutation. If the given permutation is the lexicographically least permutation, then print the input permutation itself. 

Input Format: 

First line is the test cases and second line contains value of integer n: 1 ≤ n ≤ 1,000,000 
third line is a space separated list of integers 1 2 ... n permuted in some random order 

Output Format: 

Output a single line containing a space separated list of integers which is the lexicographically preceding permutation of the input permutation.

SAMPLE INPUT
1
3
1 3 2

SAMPLE OUTPUT
1 2 3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
After attending the ProgNova contest, Peter walks out of the school to enjoy a weekend of shopping in Manhattan!

Peter has a shopping list with $m$ different items (numbered $1$ to $m$) he wants to purchase. There are $n$ shopping malls in Manhattan. Each shopping mall sells one of these $m$ items. (All the items Peter wants to buy are super rare and exclusive!) The $i$-th shopping mall is located at $(x_ i, y_ i)$ and sells only item $t_ i$.

Peter is planning for his shopping route. He starts from his school, which is located at $(0, 0)$. A move from $(x_1, y_1)$ to $(x_2, y_2)$ is said to be vertical if $|x_1 - x_2| < |y_1 - y_2|$. Otherwise, the move is horizontal. Peter always moves directly to a shopping mall or his school from his current position. He does not stop anywhere else. Peter may move to a same position multiple times. After buying all the items on the list, Peter will return to his school.

Peter hates to move vertically and wants to make as few vertical moves as possible. What is the minimum number of vertical moves Peter has to make so as to purchase all the $m$ items? Peter does not care about his total travel distance, or the number of horizontal moves he makes.

-----Input-----
The first line has two integer $n$ ($1 \leq n \leq 3\cdot 10^5$) and $m$ ($1 \leq m \leq 16$). Each of the next $n$ lines contains three integers. The $i$-th line has $x_ i$, $y_ i$ ($|x|, |y| \leq 10^9$) and $t_ i$ ($1 \leq t \leq m$). No two shopping malls share a same location and no shopping mall is located at $(0, 0)$. It is guaranteed that every of the $m$ items is sold by at least one shopping mall.

-----Output-----
Output the minimum number of vertical moves Peter has to make.

-----Examples-----
Sample Input:
3 2
1 1 2
1 2 1
-1 1 2
Sample Output:
0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are planning to build housing on a street. There are n spots available on the street on which you can build a house. The spots are labeled from 1 to n from left to right. In each spot, you can build a house with an integer height between 0 and h.

In each spot, if a house has height a, you will gain a^2 dollars from it.

The city has m zoning restrictions. The i-th restriction says that the tallest house from spots l_i to r_i (inclusive) must be at most x_i.

You would like to build houses to maximize your profit. Determine the maximum profit possible.

Input

The first line contains three integers n, h, and m (1 ≤ n,h,m ≤ 50) — the number of spots, the maximum height, and the number of restrictions.

Each of the next m lines contains three integers l_i, r_i, and x_i (1 ≤ l_i ≤ r_i ≤ n, 0 ≤ x_i ≤ h) — left and right limits (inclusive) of the i-th restriction and the maximum possible height in that range.

Output

Print a single integer, the maximum profit you can make.

Examples

Input


3 3 3
1 1 1
2 2 3
3 3 2


Output


14


Input


4 10 2
2 3 8
3 4 7


Output


262

Note

In the first example, there are 3 houses, the maximum height of a house is 3, and there are 3 restrictions. The first restriction says the tallest house between 1 and 1 must be at most 1. The second restriction says the tallest house between 2 and 2 must be at most 3. The third restriction says the tallest house between 3 and 3 must be at most 2.

In this case, it is optimal to build houses with heights [1, 3, 2]. This fits within all the restrictions. The total profit in this case is 1^2 + 3^2 + 2^2 = 14.

In the second example, there are 4 houses, the maximum height of a house is 10, and there are 2 restrictions. The first restriction says the tallest house from 2 to 3 must be at most 8. The second restriction says the tallest house from 3 to 4 must be at most 7.

In this case, it's optimal to build houses with heights [10, 8, 7, 7]. We get a profit of 10^2+8^2+7^2+7^2 = 262. Note that there are two restrictions on house 3 and both of them must be satisfied. Also, note that even though there isn't any explicit restrictions on house 1, we must still limit its height to be at most 10 (h=10).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Michael Scofield makes an escape plan to break out from Fox Rriver State Penitentiary. But Officer Bellick knows the  plan and he wants to catch Scofield red handed to prove his point to Warden Henry. At 1AM Bellick climbs up a watch tower of height h metres and monitors every movement. He knows the path which Scofield will follow. Now Bellick has new equipment called ‘Bow Arrow Net Catcher’ or BANC. This bow releases a arrow and after travelling a distance d metres a net opens up which catches the suspect. Assume the time taken by the arrow to travel the distance d as neglible and d is greater than the height of the tower. Scofield being extremely clever is hiding just below the tower. But he has to make a move. So he slowly starts to move forward and as a result Bellick spots him. But he can’t fire BANC due to its limitations. The moment Bellick finds that it is the right time to fire his weapon Scofield turns his head and sees Bellick and starts running with a constant velocity v m/s. Bellick doesn’t want him to escape so he starts coming down the tower. You are the night watchman of that tower and a great mathematician. You have to tell Bellick with what initial velocity u m/s he should go down so that he can fire BANC and catch Scofield.

Input:

The input will contain of T test cases. Every next T lines will contain h d v.

Output:

For every test Case T you need to print u rounded upto 9 decimal places.

Constraints:

0 < T < 10000

0 < h < 100000

h < d < 1000000

0 < v < 50

SAMPLE INPUT
1
9 15 3

SAMPLE OUTPUT
4.000000000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Dolphin loves programming contests. Today, he will take part in a contest in AtCoder.

In this country, 24-hour clock is used. For example, 9:00 p.m. is referred to as "21 o'clock".

The current time is A o'clock, and a contest will begin in exactly B hours.
When will the contest begin? Answer in 24-hour time.

-----Constraints-----
 - 0 \leq A,B \leq 23
 - A and B are integers.

-----Input-----
The input is given from Standard Input in the following format:
A B

-----Output-----
Print the hour of the starting time of the contest in 24-hour time.

-----Sample Input-----
9 12

-----Sample Output-----
21

In this input, the current time is 9 o'clock, and 12 hours later it will be 21 o'clock in 24-hour time.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Imagine that you are in a building that has exactly n floors. You can move between the floors in a lift. Let's number the floors from bottom to top with integers from 1 to n. Now you're on the floor number a. You are very bored, so you want to take the lift. Floor number b has a secret lab, the entry is forbidden. However, you already are in the mood and decide to make k consecutive trips in the lift.

Let us suppose that at the moment you are on the floor number x (initially, you were on floor a). For another trip between floors you choose some floor with number y (y ≠ x) and the lift travels to this floor. As you cannot visit floor b with the secret lab, you decided that the distance from the current floor x to the chosen y must be strictly less than the distance from the current floor x to floor b with the secret lab. Formally, it means that the following inequation must fulfill: |x - y| < |x - b|. After the lift successfully transports you to floor y, you write down number y in your notepad.

Your task is to find the number of distinct number sequences that you could have written in the notebook as the result of k trips in the lift. As the sought number of trips can be rather large, find the remainder after dividing the number by 1000000007 (109 + 7).

Input

The first line of the input contains four space-separated integers n, a, b, k (2 ≤ n ≤ 5000, 1 ≤ k ≤ 5000, 1 ≤ a, b ≤ n, a ≠ b).

Output

Print a single integer — the remainder after dividing the sought number of sequences by 1000000007 (109 + 7).

Examples

Input

5 2 4 1


Output

2


Input

5 2 4 2


Output

2


Input

5 3 4 1


Output

0

Note

Two sequences p1, p2, ..., pk and q1, q2, ..., qk are distinct, if there is such integer j (1 ≤ j ≤ k), that pj ≠ qj.

Notes to the samples:

  1. In the first sample after the first trip you are either on floor 1, or on floor 3, because |1 - 2| < |2 - 4| and |3 - 2| < |2 - 4|. 
  2. In the second sample there are two possible sequences: (1, 2); (1, 3). You cannot choose floor 3 for the first trip because in this case no floor can be the floor for the second trip. 
  3. In the third sample there are no sought sequences, because you cannot choose the floor for the first trip. 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Arseny likes to organize parties and invite people to it. However, not only friends come to his parties, but friends of his friends, friends of friends of his friends and so on. That's why some of Arseny's guests can be unknown to him. He decided to fix this issue using the following procedure.

At each step he selects one of his guests A, who pairwise introduces all of his friends to each other. After this action any two friends of A become friends. This process is run until all pairs of guests are friends.

Arseny doesn't want to spend much time doing it, so he wants to finish this process using the minimum number of steps. Help Arseny to do it.

Input

The first line contains two integers n and m (1 ≤ n ≤ 22; <image>) — the number of guests at the party (including Arseny) and the number of pairs of people which are friends.

Each of the next m lines contains two integers u and v (1 ≤ u, v ≤ n; u ≠ v), which means that people with numbers u and v are friends initially. It's guaranteed that each pair of friends is described not more than once and the graph of friendship is connected.

Output

In the first line print the minimum number of steps required to make all pairs of guests friends.

In the second line print the ids of guests, who are selected at each step.

If there are multiple solutions, you can output any of them.

Examples

Input

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


Output

2
2 3 

Input

4 4
1 2
1 3
1 4
3 4


Output

1
1 

Note

In the first test case there is no guest who is friend of all other guests, so at least two steps are required to perform the task. After second guest pairwise introduces all his friends, only pairs of guests (4, 1) and (4, 2) are not friends. Guest 3 or 5 can introduce them.

In the second test case guest number 1 is a friend of all guests, so he can pairwise introduce all guests in one step.

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

Reversi is a game usually played by 2 people on a 8x8 board.
Here we're only going to consider a single 8x1 row.

Players take turns placing pieces, which are black on one side and white on the
other, onto the board with their colour facing up.  If one or more of the
opponents pieces are sandwiched by the piece just played and another piece of
the current player's colour, the opponents pieces are flipped to the
current players colour.

Note that the flipping stops when the first piece of the player's colour is reached.

# Task:

Your task is to take an array of moves and convert this into a string
representing the state of the board after all those moves have been played.

# Input:

The input to your function will be an array of moves.
Moves are represented by integers from 0 to 7 corresponding to the 8 squares on the board.
Black plays first, and black and white alternate turns.
Input is guaranteed to be valid. (No duplicates, all moves in range, but array may be empty)

# Output:

8 character long string representing the final state of the board.
Use '*' for black and 'O' for white and '.' for empty.

# Examples:
```python
  reversi_row([])      # '........'
  reversi_row([3])     # '...*....'
  reversi_row([3,4])   # '...*O...'
  reversi_row([3,4,5]) # '...***..'
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The only difference between easy and hard versions is constraints.

There are n kids, each of them is reading a unique book. At the end of any day, the i-th kid will give his book to the p_i-th kid (in case of i = p_i the kid will give his book to himself). It is guaranteed that all values of p_i are distinct integers from 1 to n (i.e. p is a permutation). The sequence p doesn't change from day to day, it is fixed.

For example, if n=6 and p=[4, 6, 1, 3, 5, 2] then at the end of the first day the book of the 1-st kid will belong to the 4-th kid, the 2-nd kid will belong to the 6-th kid and so on. At the end of the second day the book of the 1-st kid will belong to the 3-th kid, the 2-nd kid will belong to the 2-th kid and so on.

Your task is to determine the number of the day the book of the i-th child is returned back to him for the first time for every i from 1 to n.

Consider the following example: p = [5, 1, 2, 4, 3]. The book of the 1-st kid will be passed to the following kids:

  * after the 1-st day it will belong to the 5-th kid, 
  * after the 2-nd day it will belong to the 3-rd kid, 
  * after the 3-rd day it will belong to the 2-nd kid, 
  * after the 4-th day it will belong to the 1-st kid. 



So after the fourth day, the book of the first kid will return to its owner. The book of the fourth kid will return to him for the first time after exactly one day.

You have to answer q independent queries.

Input

The first line of the input contains one integer q (1 ≤ q ≤ 1000) — the number of queries. Then q queries follow.

The first line of the query contains one integer n (1 ≤ n ≤ 2 ⋅ 10^5) — the number of kids in the query. The second line of the query contains n integers p_1, p_2, ..., p_n (1 ≤ p_i ≤ n, all p_i are distinct, i.e. p is a permutation), where p_i is the kid which will get the book of the i-th kid.

It is guaranteed that ∑ n ≤ 2 ⋅ 10^5 (sum of n over all queries does not exceed 2 ⋅ 10^5).

Output

For each query, print the answer on it: n integers a_1, a_2, ..., a_n, where a_i is the number of the day the book of the i-th child is returned back to him for the first time in this query.

Example

Input


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


Output


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

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 $500000$ integers (numbered from $1$ to $500000$). Initially all elements of $a$ are zero.

You have to process two types of queries to this array:  $1$ $x$ $y$ — increase $a_x$ by $y$;  $2$ $x$ $y$ — compute $\sum\limits_{i \in R(x, y)} a_i$, where $R(x, y)$ is the set of all integers from $1$ to $500000$ which have remainder $y$ modulo $x$. 

Can you process all the queries?


-----Input-----

The first line contains one integer $q$ ($1 \le q \le 500000$) — the number of queries.

Then $q$ lines follow, each describing a query. The $i$-th line contains three integers $t_i$, $x_i$ and $y_i$ ($1 \le t_i \le 2$). If $t_i = 1$, then it is a query of the first type, $1 \le x_i \le 500000$, and $-1000 \le y_i \le 1000$. If $t_i = 2$, then it it a query of the second type, $1 \le x_i \le 500000$, and $0 \le y_i < x_i$.

It is guaranteed that there will be at least one query of type $2$.


-----Output-----

For each query of type $2$ print one integer — the answer to it.


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

Output
4
4
0

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