vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: Arthur and Questions

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
After bracket sequences Arthur took up number theory. He has got a new favorite sequence of length *n* (*a*1,<=*a*2,<=...,<=*a**n*), consisting of integers and integer *k*, not exceeding *n*.

This sequence had the following property: if you write out the sums of all its segments consisting of *k* consecutive elements (*a*1 <=+<= *a*2 ... <=+<= *a**k*,<= *a*2 <=+<= *a*3 <=+<= ... <=+<= *a**k*<=+<=1,<= ...,<= *a**n*<=-<=*k*<=+<=1 <=+<= *a**n*<=-<=*k*<=+<=2 <=+<= ... <=+<= *a**n*), then those numbers will form strictly increasing sequence.

For example, for the following sample: *n*<==<=5,<= *k*<==<=3,<= *a*<==<=(1,<= 2,<= 4,<= 5,<= 6) the sequence of numbers will look as follows: (1 <=+<= 2 <=+<= 4,<= 2 <=+<= 4 <=+<= 5,<= 4 <=+<= 5 <=+<= 6) = (7,<= 11,<= 15), that means that sequence *a* meets the described property. 

Obviously the sequence of sums will have *n*<=-<=*k*<=+<=1 elements.

Somebody (we won't say who) replaced some numbers in Arthur's sequence by question marks (if this number is replaced, it is replaced by exactly one question mark). We need to restore the sequence so that it meets the required property and also minimize the sum |*a**i*|, where |*a**i*| is the absolute value of *a**i*.

Input Specification:
The first line contains two integers *n* and *k* (1<=≤<=*k*<=≤<=*n*<=≤<=105), showing how many numbers are in Arthur's sequence and the lengths of segments respectively.

The next line contains *n* space-separated elements *a**i* (1<=≤<=*i*<=≤<=*n*).

If *a**i* <==<= ?, then the *i*-th element of Arthur's sequence was replaced by a question mark. 

Otherwise, *a**i* (<=-<=109<=≤<=*a**i*<=≤<=109) is the *i*-th element of Arthur's sequence.

Output Specification:
If Arthur is wrong at some point and there is no sequence that could fit the given information, print a single string "Incorrect sequence" (without the quotes).

Otherwise, print *n* integers — Arthur's favorite sequence. If there are multiple such sequences, print the sequence with the minimum sum |*a**i*|, where |*a**i*| is the absolute value of *a**i*. If there are still several such sequences, you are allowed to print any of them. Print the elements of the sequence without leading zeroes.

Demo Input:
['3 2\n? 1 2\n', '5 1\n-10 -9 ? -7 -6\n', '5 3\n4 6 7 2 9\n']

Demo Output:
['0 1 2 \n', '-10 -9 -8 -7 -6 \n', 'Incorrect sequence\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
ZS the Coder and Chris the Baboon are travelling to Udayland! To get there, they have to get on the special IOI bus. The IOI bus has n rows of seats. There are 4 seats in each row, and the seats are separated into pairs by a walkway. When ZS and Chris came, some places in the bus was already occupied.

ZS and Chris are good friends. They insist to get a pair of neighbouring empty seats. Two seats are considered neighbouring if they are in the same row and in the same pair. Given the configuration of the bus, can you help ZS and Chris determine where they should sit?


-----Input-----

The first line of the input contains a single integer n (1 ≤ n ≤ 1000) — the number of rows of seats in the bus.

Then, n lines follow. Each line contains exactly 5 characters, the first two of them denote the first pair of seats in the row, the third character denotes the walkway (it always equals '|') and the last two of them denote the second pair of seats in the row. 

Each character, except the walkway, equals to 'O' or to 'X'. 'O' denotes an empty seat, 'X' denotes an occupied seat. See the sample cases for more details. 


-----Output-----

If it is possible for Chris and ZS to sit at neighbouring empty seats, print "YES" (without quotes) in the first line. In the next n lines print the bus configuration, where the characters in the pair of seats for Chris and ZS is changed with characters '+'. Thus the configuration should differ from the input one by exactly two charaters (they should be equal to 'O' in the input and to '+' in the output).

If there is no pair of seats for Chris and ZS, print "NO" (without quotes) in a single line.

If there are multiple solutions, you may print any of them.


-----Examples-----
Input
6
OO|OX
XO|XX
OX|OO
XX|OX
OO|OO
OO|XX

Output
YES
++|OX
XO|XX
OX|OO
XX|OX
OO|OO
OO|XX

Input
4
XO|OX
XO|XX
OX|OX
XX|OX

Output
NO

Input
5
XX|XX
XX|XX
XO|OX
XO|OO
OX|XO

Output
YES
XX|XX
XX|XX
XO|OX
XO|++
OX|XO



-----Note-----

Note that the following is an incorrect configuration for the first sample case because the seats must be in the same pair.

O+|+X

XO|XX

OX|OO

XX|OX

OO|OO

OO|XX

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vasya follows a basketball game and marks the distances from which each team makes a throw. He knows that each successful throw has value of either 2 or 3 points. A throw is worth 2 points if the distance it was made from doesn't exceed some value of d meters, and a throw is worth 3 points if the distance is larger than d meters, where d is some non-negative integer.

Vasya would like the advantage of the points scored by the first team (the points of the first team minus the points of the second team) to be maximum. For that he can mentally choose the value of d. Help him to do that.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 2·10^5) — the number of throws of the first team. Then follow n integer numbers — the distances of throws a_{i} (1 ≤ a_{i} ≤ 2·10^9). 

Then follows number m (1 ≤ m ≤ 2·10^5) — the number of the throws of the second team. Then follow m integer numbers — the distances of throws of b_{i} (1 ≤ b_{i} ≤ 2·10^9).


-----Output-----

Print two numbers in the format a:b — the score that is possible considering the problem conditions where the result of subtraction a - b is maximum. If there are several such scores, find the one in which number a is maximum.


-----Examples-----
Input
3
1 2 3
2
5 6

Output
9:6

Input
5
6 7 8 9 10
5
1 2 3 4 5

Output
15:10

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vasya has several phone books, in which he recorded the telephone numbers of his friends. Each of his friends can have one or several phone numbers.

Vasya decided to organize information about the phone numbers of friends. You will be given n strings — all entries from Vasya's phone books. Each entry starts with a friend's name. Then follows the number of phone numbers in the current entry, and then the phone numbers themselves. It is possible that several identical phones are recorded in the same record.

Vasya also believes that if the phone number a is a suffix of the phone number b (that is, the number b ends up with a), and both numbers are written by Vasya as the phone numbers of the same person, then a is recorded without the city code and it should not be taken into account.

The task is to print organized information about the phone numbers of Vasya's friends. It is possible that two different people have the same number. If one person has two numbers x and y, and x is a suffix of y (that is, y ends in x), then you shouldn't print number x. If the number of a friend in the Vasya's phone books is recorded several times in the same format, it is necessary to take it into account exactly once.

Read the examples to understand statement and format of the output better.

Input

First line contains the integer n (1 ≤ n ≤ 20) — number of entries in Vasya's phone books. 

The following n lines are followed by descriptions of the records in the format described in statement. Names of Vasya's friends are non-empty strings whose length does not exceed 10. They consists only of lowercase English letters. Number of phone numbers in one entry is not less than 1 is not more than 10. The telephone numbers consist of digits only. If you represent a phone number as a string, then its length will be in range from 1 to 10. Phone numbers can contain leading zeros.

Output

Print out the ordered information about the phone numbers of Vasya's friends. First output m — number of friends that are found in Vasya's phone books.

The following m lines must contain entries in the following format "name number_of_phone_numbers phone_numbers". Phone numbers should be separated by a space. Each record must contain all the phone numbers of current friend.

Entries can be displayed in arbitrary order, phone numbers for one record can also be printed in arbitrary order.

Examples

Input

2
ivan 1 00123
masha 1 00123


Output

2
masha 1 00123 
ivan 1 00123 


Input

3
karl 2 612 12
petr 1 12
katya 1 612


Output

3
katya 1 612 
petr 1 12 
karl 1 612 


Input

4
ivan 3 123 123 456
ivan 2 456 456
ivan 8 789 3 23 6 56 9 89 2
dasha 2 23 789


Output

2
dasha 2 23 789 
ivan 4 789 123 2 456 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Denis holds a Geometers Anonymous Club meeting in SIS. He has prepared n convex polygons numbered from 1 to n for the club. He plans to offer members of the club to calculate Minkowski sums of these polygons. More precisely, he plans to give q tasks, the i-th of them asks to calculate the sum of Minkowski of polygons with indices from l_i to r_i inclusive.

The sum of Minkowski of two sets A and B is the set C = \\{a + b : a ∈ A, b ∈ B\}. It can be proven that if A and B are convex polygons then C will also be a convex polygon.

<image> Sum of two convex polygons 

To calculate the sum of Minkowski of p polygons (p > 2), you need to calculate the sum of Minkowski of the first p - 1 polygons, and then calculate the sum of Minkowski of the resulting polygon and the p-th polygon.

For the convenience of checking answers, Denis has decided to prepare and calculate the number of vertices in the sum of Minkowski for each task he prepared. Help him to do it.

Input

The first line of the input contains one integer n — the number of convex polygons Denis prepared (1 ≤ n ≤ 100 000).

Then n convex polygons follow. The description of the i-th polygon starts with one integer k_i — the number of vertices in the i-th polygon (3 ≤ k_i). The next k_i lines contain two integers x_{ij}, y_{ij} each — coordinates of vertices of the i-th polygon in counterclockwise order (|x_{ij}|, |y_{ij}| ≤ 10 ^ 9).

It is guaranteed, that there are no three consecutive vertices lying on the same line. The total number of vertices over all polygons does not exceed 300 000.

The following line contains one integer q — the number of tasks (1 ≤ q ≤ 100 000). The next q lines contain descriptions of tasks. Description of the i-th task contains two integers l_i and r_i (1 ≤ l_i ≤ r_i ≤ n).

Output

For each task print a single integer — the number of vertices in the sum of Minkowski of polygons with indices from l_i to r_i.

Example

Input


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


Output


5
5
6

Note

Description of the example:

<image> First, second and third polygons from the example  <image> Minkowski sums of the first and second, the second and third and all polygons correspondingly 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Adarsh likes divisibility very much  , but this time he wants to test his capability.
He gave himself a number N and tried to find the smallest number which is completely divisible by all numbers from 1 to N(inclusive).
As the result can be very large he  prints his answer modulo 10^9+7.

Input:

First line contain positive integer T (number of test cases).
Next T lines contains a number N.

Output:

Print T lines of output according to given problem.

Constraints:

1 ≤ T ≤ 1000

1 ≤ N ≤ 500000

SAMPLE INPUT
2
2
3

SAMPLE OUTPUT
2
6

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
As a Hunter, you will undoubtedly face difficult obstacles during your journey. At such time, a Hunter is expected to model the situation using Mathematical models, and apply probability and statistics knowledge to overcome the situation.

Thus, the third round of the Hunter Exam is based on the following game with coins:
 - Before the game starts, Gon selects a string $g$ and Killua selects a string $k$. The two strings must contain only characters ‘H’ and ‘T’.
 - A game master will flip a coin an infinite number of times. After each flip, the result (either ‘H’ or ‘T’ — representing head or tail) is appended into a string $s$. The string $s$ is empty at the beginning of the game.
 - After some coin flip:
 - If both $g$ and $k$ become a substring of $s$, the game ends in a draw.
 - If only $g$ becomes a substring of $s$, Gon wins, and the game ends.
 - If only $k$ becomes a substring of $s$, Killua wins, and the game ends.
 - Gon and Killua only have finite amount of time. They will stop the game in a draw after $10^{100}$ turns.

Please calculate the probability that Gon wins.

-----Input-----
The input contains exactly three lines:
 - The first line contains the string $g$.
 - The second line contains the string $k$.
 - The third line contains a real number $p$ with exactly one digit after the decimal point — the probability that a coin flip will result in head $(0 < p < 1)$.

The length of $g$ and $k$ are at most $20$. $g$ and $k$ are non-empty, and contain only characters ‘H’ and ‘T’.

-----Output-----
The output must contain a single number — the probability that Gon wins.

Your answer will be considered correct if its relative or absolute error doesn’t exceed $10^{-6}$.

Namely: let’s assume that your answer is $a$, and the answer of the jury is $b$. The checker program will consider your answer correct, if $\frac{|a-b|}{max(1,b)} \leq 10^{-6}$.

-----Examples-----
Sample Input:
H
T
0.5
Sample Output:
0.5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are $n$ detachments on the surface, numbered from $1$ to $n$, the $i$-th detachment is placed in a point with coordinates $(x_i, y_i)$. All detachments are placed in different points.

Brimstone should visit each detachment at least once. You can choose the detachment where Brimstone starts.

To move from one detachment to another he should first choose one of four directions of movement (up, right, left or down) and then start moving with the constant speed of one unit interval in a second until he comes to a detachment. After he reaches an arbitrary detachment, he can repeat the same process.

Each $t$ seconds an orbital strike covers the whole surface, so at that moment Brimstone should be in a point where some detachment is located. He can stay with any detachment as long as needed.

Brimstone is a good commander, that's why he can create at most one detachment and place it in any empty point with integer coordinates he wants before his trip. Keep in mind that Brimstone will need to visit this detachment, too.

Help Brimstone and find such minimal $t$ that it is possible to check each detachment. If there is no such $t$ report about it.


-----Input-----

The first line contains a single integer $n$ $(2 \le n \le 1000)$ — the number of detachments.

In each of the next $n$ lines there is a pair of integers $x_i$, $y_i$ $(|x_i|, |y_i| \le 10^9)$ — the coordinates of $i$-th detachment.

It is guaranteed that all points are different.


-----Output-----

Output such minimal integer $t$ that it is possible to check all the detachments adding at most one new detachment.

If there is no such $t$, print $-1$.


-----Examples-----
Input
4
100 0
0 100
-100 0
0 -100

Output
100
Input
7
0 2
1 0
-3 0
0 -2
-1 -1
-1 -3
-2 -3

Output
-1
Input
5
0 0
0 -1
3 0
-2 0
-2 1

Output
2
Input
5
0 0
2 0
0 -1
-2 0
-2 1

Output
2


-----Note-----

In the first test it is possible to place a detachment in $(0, 0)$, so that it is possible to check all the detachments for $t = 100$. It can be proven that it is impossible to check all detachments for $t < 100$; thus the answer is $100$.

In the second test, there is no such $t$ that it is possible to check all detachments, even with adding at most one new detachment, so the answer is $-1$.

In the third test, it is possible to place a detachment in $(1, 0)$, so that Brimstone can check all the detachments for $t = 2$. It can be proven that it is the minimal such $t$.

In the fourth test, there is no need to add any detachments, because the answer will not get better ($t = 2$). It can be proven that it is the minimal such $t$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Takahashi made N problems for competitive programming.
The problems are numbered 1 to N, and the difficulty of Problem i is represented as an integer d_i (the higher, the harder).
He is dividing the problems into two categories by choosing an integer K, as follows:
 - A problem with difficulty K or higher will be for ARCs.
 - A problem with difficulty lower than K will be for ABCs.
How many choices of the integer K make the number of problems for ARCs and the number of problems for ABCs the same?

-----Problem Statement-----
 - 2 \leq N \leq 10^5
 - N is an even number.
 - 1 \leq d_i \leq 10^5
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N
d_1 d_2 ... d_N

-----Output-----
Print the number of choices of the integer K that make the number of problems for ARCs and the number of problems for ABCs the same.

-----Sample Input-----
6
9 1 4 4 6 7

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

If we choose K=5 or 6, Problem 1, 5, and 6 will be for ARCs, Problem 2, 3, and 4 will be for ABCs, and the objective is achieved.
Thus, the answer is 2.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vasya the Great Magician and Conjurer loves all kinds of miracles and wizardry. In one wave of a magic wand he can turn an object into something else. But, as you all know, there is no better magic in the Universe than the magic of numbers. That's why Vasya adores math and spends a lot of time turning some numbers into some other ones.

This morning he has n cards with integers lined up in front of him. Each integer is not less than 1, but not greater than l. When Vasya waves his magic wand, two rightmost cards vanish from the line and a new card magically appears in their place. It contains the difference between the left and the right numbers on the two vanished cards. Vasya was very interested to know what would happen next, and so he waved with his magic wand on and on, until the table had a single card left.

Suppose that Vasya originally had the following cards: 4, 1, 1, 3 (listed from left to right). Then after the first wave the line would be: 4, 1, -2, and after the second one: 4, 3, and after the third one the table would have a single card with number 1.

Please note that in spite of the fact that initially all the numbers on the cards were not less than 1 and not greater than l, the numbers on the appearing cards can be anything, no restrictions are imposed on them.

It is now evening. Vasya is very tired and wants to return everything back, but does not remember which cards he had in the morning. He only remembers that there were n cards, they contained integers from 1 to l, and after all magical actions he was left with a single card containing number d.

Help Vasya to recover the initial set of cards with numbers.

Input

The single line contains three space-separated integers: n (2 ≤ n ≤ 100) — the initial number of cards on the table, d (|d| ≤ 104) — the number on the card that was left on the table after all the magical actions, and l (1 ≤ l ≤ 100) — the limits for the initial integers.

Output

If Vasya is mistaken, that is, if there doesn't exist a set that meets the requirements given in the statement, then print a single number -1, otherwise print the sought set containing n integers from 1 to l. Separate the integers by spaces. Print the integers in the order, in which they were written on the cards from left to right. If there are several suitable sets of numbers, you can print any of them.

Examples

Input

3 3 2


Output

2 1 2 

Input

5 -4 3


Output

-1


Input

5 -4 4


Output

2 4 1 4 1

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. You should answer q queries. Each query is a pair (l_i, r_i), and you should calculate f(l_i, r_i).

Let's denote m_{l, r} as the position of the maximum in subsegment p_l, p_{l+1}, ..., p_r.

Then f(l, r) = (r - l + 1) + f(l, m_{l,r} - 1) + f(m_{l,r} + 1, r) if l ≤ r or 0 otherwise.

Input

The first line contains two integers n and q (1 ≤ n ≤ 10^6, 1 ≤ q ≤ 10^6) — the size of the permutation p and the number of queries.

The second line contains n pairwise distinct integers p_1, p_2, ..., p_n (1 ≤ p_i ≤ n, p_i ≠ p_j for i ≠ j) — permutation p.

The third line contains q integers l_1, l_2, ..., l_q — the first parts of the queries.

The fourth line contains q integers r_1, r_2, ..., r_q — the second parts of the queries.

It's guaranteed that 1 ≤ l_i ≤ r_i ≤ n for all queries.

Output

Print q integers — the values f(l_i, r_i) for the corresponding queries.

Example

Input


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


Output


1 6 8 5 1 

Note

Description of the queries: 

  1. f(2, 2) = (2 - 2 + 1) + f(2, 1) + f(3, 2) = 1 + 0 + 0 = 1; 
  2. f(1, 3) = (3 - 1 + 1) + f(1, 2) + f(4, 3) = 3 + (2 - 1 + 1) + f(1, 0) + f(2, 2) = 3 + 2 + (2 - 2 + 1) = 6; 
  3. f(1, 4) = (4 - 1 + 1) + f(1, 2) + f(4, 4) = 4 + 3 + 1 = 8; 
  4. f(2, 4) = (4 - 2 + 1) + f(2, 2) + f(4, 4) = 3 + 1 + 1 = 5; 
  5. f(1, 1) = (1 - 1 + 1) + 0 + 0 = 1. 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In Takaha-shi, the capital of Republic of AtCoder, there are N roads extending east and west, and M roads extending north and south. There are no other roads. The i-th east-west road from the north and the j-th north-south road from the west cross at the intersection (i, j). Two east-west roads do not cross, nor do two north-south roads. The distance between two adjacent roads in the same direction is 1.

Each road is one-way; one can only walk in one direction. The permitted direction for each road is described by a string S of length N and a string T of length M, as follows:

* If the i-th character in S is `W`, one can only walk westward along the i-th east-west road from the north;
* If the i-th character in S is `E`, one can only walk eastward along the i-th east-west road from the north;
* If the i-th character in T is `N`, one can only walk northward along the i-th north-south road from the west;
* If the i-th character in T is `S`, one can only walk southward along the i-th south-west road from the west.



Process the following Q queries:

* In the i-th query, a_i, b_i, c_i and d_i are given. What is the minimum distance to travel to reach the intersection (c_i, d_i) from the intersection (a_i, b_i) by walking along the roads?

Constraints

* 2 \leq N \leq 100000
* 2 \leq M \leq 100000
* 2 \leq Q \leq 200000
* |S| = N
* S consists of `W` and `E`.
* |T| = M
* T consists of `N` and `S`.
* 1 \leq a_i \leq N
* 1 \leq b_i \leq M
* 1 \leq c_i \leq N
* 1 \leq d_i \leq M
* (a_i, b_i) \neq (c_i, d_i)

Input

Input is given from Standard Input in the following format:


N M Q
S
T
a_1 b_1 c_1 d_1
a_2 b_2 c_2 d_2
:
a_Q b_Q c_Q d_Q


Output

In the i-th line, print the response to the i-th query. If the intersection (c_i, d_i) cannot be reached from the intersection (a_i, b_i) by walking along the roads, print `-1` instead.

Examples

Input

4 5 4
EEWW
NSNNS
4 1 1 4
1 3 1 2
4 2 3 2
3 3 3 5


Output

6
11
5
4


Input

3 3 2
EEE
SSS
1 1 3 3
3 3 1 1


Output

4
-1


Input

9 7 10
EEEEEWEWW
NSSSNSN
4 6 9 2
3 7 6 7
7 5 3 5
1 1 8 1
4 3 5 4
7 4 6 4
2 5 8 6
6 6 2 7
2 4 7 5
7 2 9 7


Output

9
-1
4
9
2
3
7
7
6
-1

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