vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Little Dima has two sequences of points with integer coordinates: sequence (a_1, 1), (a_2, 2), ..., (a_{n}, n) and sequence (b_1, 1), (b_2, 2), ..., (b_{n}, n).

Now Dima wants to count the number of distinct sequences of points of length 2·n that can be assembled from these sequences, such that the x-coordinates of points in the assembled sequence will not decrease. Help him with that. Note that each element of the initial sequences should be used exactly once in the assembled sequence.

Dima considers two assembled sequences (p_1, q_1), (p_2, q_2), ..., (p_{2·}n, q_{2·}n) and (x_1, y_1), (x_2, y_2), ..., (x_{2·}n, y_{2·}n) distinct, if there is such i (1 ≤ i ≤ 2·n), that (p_{i}, q_{i}) ≠ (x_{i}, y_{i}).

As the answer can be rather large, print the remainder from dividing the answer by number m.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 10^5). The second line contains n integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^9). The third line contains n integers b_1, b_2, ..., b_{n} (1 ≤ b_{i} ≤ 10^9). The numbers in the lines are separated by spaces.

The last line contains integer m (2 ≤ m ≤ 10^9 + 7).


-----Output-----

In the single line print the remainder after dividing the answer to the problem by number m. 


-----Examples-----
Input
1
1
2
7

Output
1

Input
2
1 2
2 3
11

Output
2



-----Note-----

In the first sample you can get only one sequence: (1, 1), (2, 1). 

In the second sample you can get such sequences : (1, 1), (2, 2), (2, 1), (3, 2); (1, 1), (2, 1), (2, 2), (3, 2). Thus, the answer is 2.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given two integers A and B.

Print a grid where each square is painted white or black that satisfies the following conditions, in the format specified in Output section:

* Let the size of the grid be h \times w (h vertical, w horizontal). Both h and w are at most 100.
* The set of the squares painted white is divided into exactly A connected components.
* The set of the squares painted black is divided into exactly B connected components.



It can be proved that there always exist one or more solutions under the conditions specified in Constraints section. If there are multiple solutions, any of them may be printed.

Constraints

* 1 \leq A \leq 500
* 1 \leq B \leq 500

Input

Input is given from Standard Input in the following format:


A B


Output

Output should be in the following format:

* In the first line, print integers h and w representing the size of the grid you constructed, with a space in between.
* Then, print h more lines. The i-th (1 \leq i \leq h) of these lines should contain a string s_i as follows:
* If the square at the i-th row and j-th column (1 \leq j \leq w) in the grid is painted white, the j-th character in s_i should be `.`.
* If the square at the i-th row and j-th column (1 \leq j \leq w) in the grid is painted black, the j-th character in s_i should be `#`.

Examples

Input

2 3


Output

3 3
##.
..#
#.#


Input

7 8


Output

3 5
.#.#
.#.#.
.#.#


Input

1 1


Output

4 2
..
.


Input

3 14


Output

8 18
..................
..................
....##.......####.
....#.#.....#.....
...#...#....#.....
..#.###.#...#.....
.#.......#..#.....
.........#..####.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Fake News (medium)

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Thanks to your help, Heidi is confident that no one can fool her. She has now decided to post some fake news on the HC2 Facebook page. However, she wants to be able to communicate to the HC2 committee that the post is fake, using some secret phrase hidden in the post as a subsequence. To make this method foolproof, she wants the phrase to appear *n* times in the post. She is asking you to design a post (string) *s* and a hidden phrase *p* such that *p* appears in *s* as a subsequence exactly *n* times.

Input Specification:
The first and only line of input contains a single integer *n* (1<=≤<=*n*<=≤<=1<=000<=000).

Output Specification:
The output should contain two nonempty strings *s* and *p* separated by a single space. Each string should be composed of letters (a-z and A-Z: both lowercase and uppercase are allowed) and have length at most 200. The number of occurrences of *p* in *s* as a subsequence should be exactly *n*. If there are many possible solutions, output any of them. It is guaranteed that at least one solution exists.

Demo Input:
['2\n', '4\n', '6\n']

Demo Output:
['hHheidi Hei', 'bbbba ba', 'aaabb ab']

Note:
An occurrence of *p* as a subsequence in *s* should be thought of as a set of positions in *s* such that the letters at these positions, in order, form *p*. The number of occurences is thus the number of such sets. For example, ab appears 6 times as a subsequence in aaabb, for the following sets of positions: {1, 4}, {1, 5}, {2, 4}, {2, 5}, {3, 4}, {3, 5} (that is, we should choose one of the a's and one of the b's).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Jzzhu is the president of country A. There are n cities numbered from 1 to n in his country. City 1 is the capital of A. Also there are m roads connecting the cities. One can go from city u_{i} to v_{i} (and vise versa) using the i-th road, the length of this road is x_{i}. Finally, there are k train routes in the country. One can use the i-th train route to go from capital of the country to city s_{i} (and vise versa), the length of this route is y_{i}.

Jzzhu doesn't want to waste the money of the country, so he is going to close some of the train routes. Please tell Jzzhu the maximum number of the train routes which can be closed under the following condition: the length of the shortest path from every city to the capital mustn't change.


-----Input-----

The first line contains three integers n, m, k (2 ≤ n ≤ 10^5; 1 ≤ m ≤ 3·10^5; 1 ≤ k ≤ 10^5).

Each of the next m lines contains three integers u_{i}, v_{i}, x_{i} (1 ≤ u_{i}, v_{i} ≤ n; u_{i} ≠ v_{i}; 1 ≤ x_{i} ≤ 10^9).

Each of the next k lines contains two integers s_{i} and y_{i} (2 ≤ s_{i} ≤ n; 1 ≤ y_{i} ≤ 10^9).

It is guaranteed that there is at least one way from every city to the capital. Note, that there can be multiple roads between two cities. Also, there can be multiple routes going to the same city from the capital.


-----Output-----

Output a single integer representing the maximum number of the train routes which can be closed.


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

Output
2

Input
2 2 3
1 2 2
2 1 3
2 1
2 2
2 3

Output
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Anki started a new restaurant in Jalpaiguri. As a perfectionist, she wants no complaint from any of the customers.
So she decided to promise every customer with accurate time for waiting after the order is placed. Can you help Anki run her restaurant better by designing a program which will help her track the orders and hence calculate the accurate time?
But there is a problem. There are N types of dishes served there. For each item, the chef takes a certain time (varies from dish to dish) to prepare the dish and a stipulated time to rest after cooking it.

Note: Each customer orders only one dish.

Input format
The first line has a single integer T the number of test cases. Every test case comprises 4 lines.
First line contains N, C and R the no of dishes, the number of customers and relaxation time of the chef in seconds respectively.
Next line is followed by N integers signifying the preparation time for the i^th dish.
Next line contains C integers signifying the dish each customer ordered.
Next line contains the time of arrival of each customer in seconds considering the initial time to be 0. (i+1)^th customer does not arrive before i^th customer).

Note: All arrays have been treated to be 1-indexed.

Output format
Display C integers where each integer displays the time in seconds a customer has to wait for getting his dish cooked.

Constraints

1 ≤ T, N, C, R ≤ 100

SAMPLE INPUT
1
3 4 1
3 3 3
3 2 1 3
3 10 12 12

SAMPLE OUTPUT
3 3 5 9

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This is an interactive problem!

As part of your contribution in the Great Bubble War, you have been tasked with finding the newly built enemy fortress. The world you live in is a giant 10^9 × 10^9 grid, with squares having both coordinates between 1 and 10^9. 

You know that the enemy base has the shape of a rectangle, with the sides parallel to the sides of the grid. The people of your world are extremely scared of being at the edge of the world, so you know that the base doesn't contain any of the squares on the edges of the grid (the x or y coordinate being 1 or 10^9). 

To help you locate the base, you have been given a device that you can place in any square of the grid, and it will tell you the manhattan distance to the closest square of the base. The manhattan distance from square (a, b) to square (p, q) is calculated as |a−p|+|b−q|. If you try to place the device inside the enemy base, you will be captured by the enemy. Because of this, you need to make sure to never place the device inside the enemy base. 

Unfortunately, the device is powered by a battery and you can't recharge it. This means that you can use the device at most 40 times. 

Input

The input contains the answers to your queries. 

Interaction

Your code is allowed to place the device on any square in the grid by writing "? i j" (1 ≤ i,j ≤ 10^9). In return, it will recieve the manhattan distance to the closest square of the enemy base from square (i,j) or -1 if the square you placed the device on is inside the enemy base or outside the grid. 

If you recieve -1 instead of a positive number, exit immidiately and you will see the wrong answer verdict. Otherwise, you can get an arbitrary verdict because your solution will continue to read from a closed stream.

Your solution should use no more than 40 queries. 

Once you are sure where the enemy base is located, you should print "! x y p q" (1 ≤ x ≤ p≤ 10^9, 1 ≤ y ≤ q≤ 10^9), where (x, y) is the square inside the enemy base with the smallest x and y coordinates, and (p, q) is the square inside the enemy base with the largest x and y coordinates. Note that answering doesn't count as one of the 40 queries.

After printing a query or printing the answer, do not forget to output end of line and flush the output. Otherwise, you will get idleness limit exceeded. To do this, use: 

  * fflush(stdout) or cout.flush() in C++; 
  * System.out.flush() in Java; 
  * flush(output) in Pascal; 
  * stdout.flush() in Python; 
  * See the documentation for other languages.

Example

Input


1
1
2
1


Output


? 2 2
? 5 5
? 4 7
? 1 5
! 2 3 4 5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
AtCoDeer is thinking of painting an infinite two-dimensional grid in a checked pattern of side K.
Here, a checked pattern of side K is a pattern where each square is painted black or white so that each connected component of each color is a K × K square.
Below is an example of a checked pattern of side 3:
AtCoDeer has N desires.
The i-th desire is represented by x_i, y_i and c_i.
If c_i is B, it means that he wants to paint the square (x_i,y_i) black; if c_i is W, he wants to paint the square (x_i,y_i) white.
At most how many desires can he satisfy at the same time?

-----Constraints-----
 - 1 ≤ N ≤ 10^5
 - 1 ≤ K ≤ 1000
 - 0 ≤ x_i ≤ 10^9
 - 0 ≤ y_i ≤ 10^9
 - If i ≠ j, then (x_i,y_i) ≠ (x_j,y_j).
 - c_i is B or W.
 - N, K, x_i and y_i are integers.

-----Input-----
Input is given from Standard Input in the following format:
N K
x_1 y_1 c_1
x_2 y_2 c_2
:
x_N y_N c_N

-----Output-----
Print the maximum number of desires that can be satisfied at the same time.

-----Sample Input-----
4 3
0 1 W
1 2 W
5 3 B
5 4 B

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

He can satisfy all his desires by painting as shown in the example above.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
The main walking trail in Geraldion is absolutely straight, and it passes strictly from the north to the south, it is so long that no one has ever reached its ends in either of the two directions. The Geraldionians love to walk on this path at any time, so the mayor of the city asked the Herald to illuminate this path with a few spotlights. The spotlights have already been delivered to certain places and Gerald will not be able to move them. Each spotlight illuminates a specific segment of the path of the given length, one end of the segment is the location of the spotlight, and it can be directed so that it covers the segment to the south or to the north of spotlight.

The trail contains a monument to the mayor of the island, and although you can walk in either directions from the monument, no spotlight is south of the monument.

You are given the positions of the spotlights and their power. Help Gerald direct all the spotlights so that the total length of the illuminated part of the path is as much as possible.

Input Specification:
The first line contains integer *n* (1<=≤<=*n*<=≤<=100) — the number of spotlights. Each of the *n* lines contains two space-separated integers, *a**i* and *l**i* (0<=≤<=*a**i*<=≤<=108, 1<=≤<=*l**i*<=≤<=108). Number *a**i* shows how much further the *i*-th spotlight to the north, and number *l**i* shows the length of the segment it illuminates.

It is guaranteed that all the *a**i*'s are distinct.

Output Specification:
Print a single integer — the maximum total length of the illuminated part of the path.

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

Demo Output:
['5\n', '9\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
How many infinite sequences a_1, a_2, ... consisting of {{1, ... ,n}} satisfy the following conditions?
 - The n-th and subsequent elements are all equal. That is, if n \leq i,j, a_i = a_j.
 - For every integer i, the a_i elements immediately following the i-th element are all equal. That is, if i < j < k\leq i+a_i, a_j = a_k.
Find the count modulo 10^9+7.

-----Constraints-----
 - 1 \leq n \leq 10^6

-----Input-----
Input is given from Standard Input in the following format:
n

-----Output-----
Print how many sequences satisfy the conditions, modulo 10^9+7.

-----Sample Input-----
2

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

The four sequences that satisfy the conditions are:
 - 1, 1, 1, ...
 - 1, 2, 2, ...
 - 2, 1, 1, ...
 - 2, 2, 2, ...

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Author note: I think some of you might remember the problem "Two Melodies" from Eductational Codeforces Round 22. Now it's time to make it a bit more difficult!

Alice is a composer, and recently she had recorded two tracks that became very popular. Now she has got a lot of fans who are waiting for new tracks. 

This time Alice wants to form four melodies for her tracks.

Alice has a sheet with *n* notes written on it. She wants to take four such non-empty non-intersecting subsequences that all of them form a melody and sum of their lengths is maximal.

Subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements.

Subsequence forms a melody when each two adjacent notes either differ by 1 or are congruent modulo 7.

You should write a program which will calculate maximum sum of lengths of such four non-empty non-intersecting subsequences that all of them form a melody.

Input Specification:
The first line contains one integer number *n* (4<=≤<=*n*<=≤<=3000).

The second line contains *n* integer numbers *a*1,<=*a*2,<=...,<=*a**n* (1<=≤<=*a**i*<=≤<=105) — notes written on a sheet.

Output Specification:
Print maximum sum of lengths of such four non-empty non-intersecting subsequences that all of them form a melody.

Demo Input:
['5\n1 3 5 7 9\n', '5\n1 3 5 7 2\n']

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

Note:
In the first example it is possible to compose 4 melodies by choosing any 4 notes (and each melody will consist of only one note).

In the second example it is possible to compose one melody with 2 notes — {1, 2}. Remaining notes are used in other three melodies (one note per each melody).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Shortly before the programming contest started, Bjarki decided to update his computer. He didn’t notice anything strange until he started coding in his favorite editor, Bim (Bjarki IMproved). Usually when he’s writing in an editor and presses the backspace key a single character is erased to the left. But after the update pressing that key outputs the character <. He’s tested all the editors on his machine, Bmacs, Neobim, bjedit, NoteBjad++ and Subjark Text, but they all seem to have the same problem. He doesn’t have time to search the web for a solution, and instead decides to temporarily circumvent the issue with a simple program.

Help Bjarki write a program that takes as input the string that was written in the text editor, and outputs the string as Bjarki intended to write it. You can assume that Bjarki never intended to write the character <, and that Bjarki never pressed the backspace key in an empty line.

-----Input-----
One line containing the string that was written in the text editor. The length of the string is at most $10^6$, and it will only contain lowercase letters from the English alphabet as well as the character <.

-----Output-----
One line containing the string as Bjarki intended to write it.

-----Examples-----
Sample Input 1:
a<bc<
Sample Output 1:
b

Sample Input 2:
foss<<rritun
Sample Output 2:
forritun

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Complete the function which takes two arguments and returns all numbers which are divisible by the given divisor. First argument is an array of `numbers` and the second is the `divisor`.

## Example

```python
divisible_by([1, 2, 3, 4, 5, 6], 2) == [2, 4, 6]
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Pasha decided to invite his friends to a tea party. For that occasion, he has a large teapot with the capacity of w milliliters and 2n tea cups, each cup is for one of Pasha's friends. The i-th cup can hold at most a_{i} milliliters of water.

It turned out that among Pasha's friends there are exactly n boys and exactly n girls and all of them are going to come to the tea party. To please everyone, Pasha decided to pour the water for the tea as follows:  Pasha can boil the teapot exactly once by pouring there at most w milliliters of water;  Pasha pours the same amount of water to each girl;  Pasha pours the same amount of water to each boy;  if each girl gets x milliliters of water, then each boy gets 2x milliliters of water. 

In the other words, each boy should get two times more water than each girl does.

Pasha is very kind and polite, so he wants to maximize the total amount of the water that he pours to his friends. Your task is to help him and determine the optimum distribution of cups between Pasha's friends.


-----Input-----

The first line of the input contains two integers, n and w (1 ≤ n ≤ 10^5, 1 ≤ w ≤ 10^9) — the number of Pasha's friends that are boys (equal to the number of Pasha's friends that are girls) and the capacity of Pasha's teapot in milliliters.

The second line of the input contains the sequence of integers a_{i} (1 ≤ a_{i} ≤ 10^9, 1 ≤ i ≤ 2n) — the capacities of Pasha's tea cups in milliliters.


-----Output-----

Print a single real number — the maximum total amount of water in milliliters that Pasha can pour to his friends without violating the given conditions. Your answer will be considered correct if its absolute or relative error doesn't exceed 10^{ - 6}.


-----Examples-----
Input
2 4
1 1 1 1

Output
3
Input
3 18
4 4 4 2 2 2

Output
18
Input
1 5
2 3

Output
4.5


-----Note-----

Pasha also has candies that he is going to give to girls but that is another task...

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e.,  [0,1,2,4,5,6,7] might become  [4,5,6,7,0,1,2]).

Find the minimum element.

You may assume no duplicate exists in the array.

Example 1:


Input: [3,4,5,1,2] 
Output: 1


Example 2:


Input: [4,5,6,7,0,1,2]
Output: 0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We guessed a permutation p consisting of n integers. The permutation of length n is the array of length n where each element from 1 to n appears exactly once. This permutation is a secret for you.

For each position r from 2 to n we chose some other index l (l < r) and gave you the segment p_l, p_{l + 1}, ..., p_r in sorted order (i.e. we rearranged the elements of this segment in a way that the elements of this segment are sorted). Thus, you are given exactly n-1 segments of the initial permutation but elements inside each segment are sorted. The segments are given to you in random order.

For example, if the secret permutation is p=[3, 1, 4, 6, 2, 5] then the possible given set of segments can be:

  * [2, 5, 6] 
  * [4, 6] 
  * [1, 3, 4] 
  * [1, 3] 
  * [1, 2, 4, 6] 



Your task is to find any suitable permutation (i.e. any permutation corresponding to the given input data). It is guaranteed that the input data corresponds to some permutation (i.e. such permutation exists).

You have to answer t independent test cases.

Input

The first line of the input contains one integer t (1 ≤ t ≤ 100) — the number of test cases. Then t test cases follow.

The first line of the test case contains one integer n (2 ≤ n ≤ 200) — the length of the permutation.

The next n-1 lines describe given segments.

The i-th line contains the description of the i-th segment. The line starts with the integer k_i (2 ≤ k_i ≤ n) — the length of the i-th segment. Then k_i integers follow. All integers in a line are distinct, sorted in ascending order, between 1 and n, inclusive.

It is guaranteed that the required p exists for each test case.

It is also guaranteed that the sum of n over all test cases does not exceed 200 (∑ n ≤ 200).

Output

For each test case, print the answer: n integers p_1, p_2, ..., p_n (1 ≤ p_i ≤ n, all p_i should be distinct) — any suitable permutation (i.e. any permutation corresponding to the test case input).

Example

Input


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


Output


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

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