vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: Collective Mindsets (hard)

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Heidi got one brain, thumbs up! But the evening isn't over yet and one more challenge awaits our dauntless agent: after dinner, at precisely midnight, the *N* attendees love to play a very risky game...

Every zombie gets a number *n**i* (1<=≤<=*n**i*<=≤<=*N*) written on his forehead. Although no zombie can see his own number, he can see the numbers written on the foreheads of all *N*<=-<=1 fellows. Note that not all numbers have to be unique (they can even all be the same). From this point on, no more communication between zombies is allowed. Observation is the only key to success. When the cuckoo clock strikes midnight, all attendees have to simultaneously guess the number on their own forehead. If at least one of them guesses his number correctly, all zombies survive and go home happily. On the other hand, if not a single attendee manages to guess his number correctly, all of them are doomed to die!

Zombies aren't very bright creatures though, and Heidi has to act fast if she does not want to jeopardize her life. She has one single option: by performing some quick surgery on the brain she managed to get from the chest, she has the ability to remotely reprogram the decision-making strategy of all attendees for their upcoming midnight game! Can you suggest a sound strategy to Heidi which, given the rules of the game, ensures that at least one attendee will guess his own number correctly, for any possible sequence of numbers on the foreheads?

Given a zombie's rank *R* and the *N*<=-<=1 numbers *n**i* on the other attendees' foreheads, your program will have to return the number that the zombie of rank *R* shall guess. Those answers define your strategy, and we will check if it is flawless or not.

Input Specification:
The first line of input contains a single integer *T* (1<=≤<=*T*<=≤<=50000): the number of scenarios for which you have to make a guess.

The *T* scenarios follow, described on two lines each: 
 -  The first line holds two integers, *N* (2<=≤<=*N*<=≤<=6), the number of attendees, and *R* (1<=≤<=*R*<=≤<=*N*), the rank of the zombie who has to make the guess. -  The second line lists *N*<=-<=1 integers: the numbers on the foreheads of all other attendees, listed in increasing order of the attendees' rank. (Every zombie knows the rank of every other zombie.)

Output Specification:
For every scenario, output a single integer: the number that the zombie of rank *R* shall guess, based on the numbers *n**i* on his *N*<=-<=1 fellows' foreheads.

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

Demo Output:
['1\n2\n2\n1\n', '5\n2\n']

Note:
For instance, if there were *N* = 2 two attendees, a successful strategy could be: 
 -  The zombie of rank 1 always guesses the number he sees on the forehead of the zombie of rank 2. -  The zombie of rank 2 always guesses the opposite of the number he sees on the forehead of the zombie of rank 1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We define a magic square to be an $n\times n$ matrix of distinct positive integers from $\mbox{1}$ to $n^2$ where the sum of any row, column, or diagonal of length $n$ is always equal to the same number:  the magic constant. 

You will be given a $3\times3$ matrix $\boldsymbol{\mathrm{~S~}}$ of integers in the inclusive range $[1,9]$. We can convert any digit $\boldsymbol{a}$ to any other digit $\boldsymbol{b}$ in the range $[1,9]$ at cost of $\left|a-b\right|$.  Given $\boldsymbol{\mathrm{~S~}}$, convert it into a magic square at minimal cost. Print this cost on a new line.

Note: The resulting magic square must contain distinct integers in the inclusive range $[1,9]$.

Example  

$s = [[5, 3, 4], [1, 5, 8], [6, 4, 2]]$  

The matrix looks like this: 

5 3 4
1 5 8
6 4 2

We can convert it to the following magic square:

8 3 4
1 5 9
6 7 2

This took three replacements at a cost of $|5-8|+|8-9|+|4-7|=7$.

Function Description

Complete the formingMagicSquare function in the editor below.  

formingMagicSquare has the following parameter(s):  

int s[3][3]: a $3\times3$ array of integers  

Returns  

int:  the minimal total cost of converting the input square to a magic square 

Input Format

Each of the $3$ lines contains three space-separated integers of row $s[i]$.  

Constraints

$s[i][j]\in[1,9]$

Sample Input 0
4 9 2
3 5 7
8 1 5

Sample Output 0
1

Explanation 0

If we change the bottom right value, $s[2][2]$, from $5$ to $\boldsymbol{6}$ at a cost of $|6-5|=1$, $\boldsymbol{\mathrm{~S~}}$ becomes a magic square at the minimum possible cost.

Sample Input 1
4 8 2
4 5 7
6 1 6

Sample Output 1
4

Explanation 1

Using 0-based indexing, if we make 

$s[0][1]$->$\mbox{9}$ at a cost of $|9-8|=1$ 
$s[\mathbf{1}][\mathbf{0}]$->$3$ at a cost of $|3-4|=1$
$s[2][0]$->$8$ at a cost of $|8-6|=2$,  

then the total cost will be $1+1+2=4$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Anya loves to fold and stick. Today she decided to do just that.

Anya has n cubes lying in a line and numbered from 1 to n from left to right, with natural numbers written on them. She also has k stickers with exclamation marks. We know that the number of stickers does not exceed the number of cubes.

Anya can stick an exclamation mark on the cube and get the factorial of the number written on the cube. For example, if a cube reads 5, then after the sticking it reads 5!, which equals 120.

You need to help Anya count how many ways there are to choose some of the cubes and stick on some of the chosen cubes at most k exclamation marks so that the sum of the numbers written on the chosen cubes after the sticking becomes equal to S. Anya can stick at most one exclamation mark on each cube. Can you do it?

Two ways are considered the same if they have the same set of chosen cubes and the same set of cubes with exclamation marks.

Input

The first line of the input contains three space-separated integers n, k and S (1 ≤ n ≤ 25, 0 ≤ k ≤ n, 1 ≤ S ≤ 1016) — the number of cubes and the number of stickers that Anya has, and the sum that she needs to get. 

The second line contains n positive integers ai (1 ≤ ai ≤ 109) — the numbers, written on the cubes. The cubes in the input are described in the order from left to right, starting from the first one. 

Multiple cubes can contain the same numbers.

Output

Output the number of ways to choose some number of cubes and stick exclamation marks on some of them so that the sum of the numbers became equal to the given number S.

Examples

Input

2 2 30
4 3


Output

1


Input

2 2 7
4 3


Output

1


Input

3 1 1
1 1 1


Output

6

Note

In the first sample the only way is to choose both cubes and stick an exclamation mark on each of them.

In the second sample the only way is to choose both cubes but don't stick an exclamation mark on any of them.

In the third sample it is possible to choose any of the cubes in three ways, and also we may choose to stick or not to stick the exclamation mark on it. So, the total number of ways is six.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We have N bags numbered 1 through N and N dishes numbered 1 through N.
Bag i contains a_i coins, and each dish has nothing on it initially.
Taro the first and Jiro the second will play a game against each other.
They will alternately take turns, with Taro the first going first.
In each player's turn, the player can make one of the following two moves:
 - When one or more bags contain coin(s): Choose one bag that contains coin(s) and one dish, then move all coins in the chosen bag onto the chosen dish. (The chosen dish may already have coins on it, or not.)
 - When no bag contains coins: Choose one dish with coin(s) on it, then remove one or more coins from the chosen dish.
The player who first becomes unable to make a move loses. Determine the winner of the game when the two players play optimally.
You are given T test cases. Solve each of them.

-----Constraints-----
 - All values in input are integers.
 - 1 \leq T \leq 10^5
 - 1 \leq N \leq 10^{5}
 - 1 \leq a_i \leq 10^9
 - In one input file, the sum of N does not exceed 2 \times 10^5.

-----Input-----
Input is given from Standard Input in the following format:
T
\mathrm{case}_1
\vdots
\mathrm{case}_T

Each case is in the following format:
N
a_1 a_2 \cdots a_N

-----Output-----
Print T lines. The i-th line should contain First if Taro the first wins in the i-th test case, and Second if Jiro the second wins in the test case.

-----Sample Input-----
3
1
10
2
1 2
21
476523737 103976339 266993 706803678 802362985 892644371 953855359 196462821 817301757 409460796 773943961 488763959 405483423 616934516 710762957 239829390 55474813 818352359 312280585 185800870 255245162

-----Sample Output-----
Second
First
Second

 - In test case 1, Jiro the second wins. Below is one sequence of moves that results in Jiro's win:
 - In Taro the first's turn, he can only choose Bag 1 and move the coins onto Dish 1.
 - In Jiro the second's turn, he can choose Dish 1 and remove all coins from it, making Taro fail to make a move and lose.
 - Note that when there is a bag that contains coin(s), a player can only make a move in which he chooses a bag that contains coin(s) and moves the coin(s) onto a dish.
 - Similarly, note that when there is no bag that contains coin(s), a player can only make a move in which he chooses a dish and removes one or more coins.

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.
Staircase detail

This is a staircase of size $n=4$:

   #
  ##
 ###
####

Its base and height are both equal to $n$.  It is drawn using # symbols and spaces. The last line is not preceded by any spaces. 

Write a program that prints a staircase of size $n$.  

Function Description

Complete the staircase function in the editor below.  

staircase has the following parameter(s):  

int n: an integer  

Print  

Print a staircase as described above.  

Input Format

A single integer, $n$, denoting the size of the staircase.

Constraints

$0<n\leq100$ .  

Output Format

Print a staircase of size $n$ using # symbols and spaces.

Note: The last line must have $\mbox{0}$ spaces in it.  

Sample Input
6 

Sample Output
     #
    ##
   ###
  ####
 #####
######

Explanation

The staircase is right-aligned, composed of # symbols and spaces, and has a height and width of $n=6$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Polycarp plans to conduct a load testing of its new project Fakebook. He already agreed with his friends that at certain points in time they will send requests to Fakebook. The load testing will last n minutes and in the i-th minute friends will send a_{i} requests.

Polycarp plans to test Fakebook under a special kind of load. In case the information about Fakebook gets into the mass media, Polycarp hopes for a monotone increase of the load, followed by a monotone decrease of the interest to the service. Polycarp wants to test this form of load.

Your task is to determine how many requests Polycarp must add so that before some moment the load on the server strictly increases and after that moment strictly decreases. Both the increasing part and the decreasing part can be empty (i. e. absent). The decrease should immediately follow the increase. In particular, the load with two equal neigbouring values is unacceptable.

For example, if the load is described with one of the arrays [1, 2, 8, 4, 3], [1, 3, 5] or [10], then such load satisfies Polycarp (in each of the cases there is an increasing part, immediately followed with a decreasing part). If the load is described with one of the arrays [1, 2, 2, 1], [2, 1, 2] or [10, 10], then such load does not satisfy Polycarp.

Help Polycarp to make the minimum number of additional requests, so that the resulting load satisfies Polycarp. He can make any number of additional requests at any minute from 1 to n.


-----Input-----

The first line contains a single integer n (1 ≤ n ≤ 100 000) — the duration of the load testing.

The second line contains n integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^9), where a_{i} is the number of requests from friends in the i-th minute of the load testing.


-----Output-----

Print the minimum number of additional requests from Polycarp that would make the load strictly increasing in the beginning and then strictly decreasing afterwards.


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

Output
6

Input
5
1 2 2 2 1

Output
1

Input
7
10 20 40 50 70 90 30

Output
0



-----Note-----

In the first example Polycarp must make two additional requests in the third minute and four additional requests in the fourth minute. So the resulting load will look like: [1, 4, 5, 6, 5]. In total, Polycarp will make 6 additional requests.

In the second example it is enough to make one additional request in the third minute, so the answer is 1.

In the third example the load already satisfies all conditions described in the statement, so the answer is 0.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are n parliamentarians in Berland. They are numbered with integers from 1 to n. It happened that all parliamentarians with odd indices are Democrats and all parliamentarians with even indices are Republicans.

New parliament assembly hall is a rectangle consisting of a × b chairs — a rows of b chairs each. Two chairs are considered neighbouring if they share as side. For example, chair number 5 in row number 2 is neighbouring to chairs number 4 and 6 in this row and chairs with number 5 in rows 1 and 3. Thus, chairs have four neighbours in general, except for the chairs on the border of the hall

We know that if two parliamentarians from one political party (that is two Democrats or two Republicans) seat nearby they spent all time discussing internal party issues.

Write the program that given the number of parliamentarians and the sizes of the hall determine if there is a way to find a seat for any parliamentarian, such that no two members of the same party share neighbouring seats.

Input

The first line of the input contains three integers n, a and b (1 ≤ n ≤ 10 000, 1 ≤ a, b ≤ 100) — the number of parliamentarians, the number of rows in the assembly hall and the number of seats in each row, respectively.

Output

If there is no way to assigns seats to parliamentarians in a proper way print -1.

Otherwise print the solution in a lines, each containing b integers. The j-th integer of the i-th line should be equal to the index of parliamentarian occupying this seat, or 0 if this seat should remain empty. If there are multiple possible solution, you may print any of them.

Examples

Input

3 2 2


Output

0 3
1 2


Input

8 4 3


Output

7 8 3
0 1 4
6 0 5
0 2 0


Input

10 2 2


Output

-1

Note

In the first sample there are many other possible solutions. For example, 
    
    
    3 2  
    0 1  
    

and 
    
    
    2 1  
    3 0  
    

The following assignment 
    
    
    3 2  
    1 0  
    

is incorrect, because parliamentarians 1 and 3 are both from Democrats party but will occupy neighbouring seats.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have a grid G containing R rows (numbered from 1 to R, top to bottom) and C columns (numbered from 1 to C, left to right) of uppercase characters. The character in the r^{th} row and the c^{th} column is denoted by G_{r, c}. You also have Q strings containing uppercase characters. For each of the string, you want to find the number of occurrences of the string in the grid.

An occurrence of string S in the grid is counted if S can be constructed by starting at one of the cells in the grid, going right 0 or more times, and then going down 0 or more times. Two occurrences are different if the set of cells used to construct the string is different. Formally, for each string S, you would like to count the number of tuples ⟨ r, c, Δ r, Δ c ⟩ such that: 

  * 1 ≤ r ≤ R and r ≤ r + Δ r ≤ R 
  * 1 ≤ c ≤ C and c ≤ c + Δ c ≤ C 
  * S = G_{r, c} G_{r, c + 1} ... G_{r, c + Δ c} G_{r + 1, c + Δ c} ... G_{r + Δ r, c + Δ c} 

Input

Input begins with a line containing three integers: R C Q (1 ≤ R, C ≤ 500; 1 ≤ Q ≤ 200 000) representing the size of the grid and the number of strings, respectively. The next R lines each contains C uppercase characters representing the grid. The c^{th} character on the r^{th} line is G_{r, c}. The next Q lines each contains a string S containing uppercase characters. The length of this string is a positive integer not more than 200 000. The sum of the length of all Q strings combined is not more than 200 000.

Output

For each query in the same order as input, output in a line an integer representing the number of occurrences of the string in the grid.

Examples

Input


3 3 5
ABC
BCD
DAB
ABC
BC
BD
AC
A


Output


2
3
1
0
2


Input


2 3 3
AAA
AAA
A
AAA
AAAAA


Output


6
4
0

Note

Explanation for the sample input/output #1

  * There are 2 occurrences of "ABC", represented by the tuples ⟨ 1, 1, 1, 1 ⟩ and ⟨ 1, 1, 0, 2 ⟩. 
  * There are 3 occurrences of "BC", represented by the tuples ⟨ 1, 2, 0, 1 ⟩, ⟨ 1, 2, 1, 0 ⟩, and ⟨ 2, 1, 0, 1 ⟩. 
  * There is 1 occurrence of "BD", represented by the tuple ⟨ 2, 1, 1, 0 ⟩. 
  * There is no occurrence of "AC". 
  * There are 2 occurrences of "A", represented by the tuples ⟨ 1, 1, 0, 0 ⟩ and ⟨ 3, 2, 0, 0 ⟩. 

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:

cba927b2484fad94fb5ff7473e9aadef.png

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.

Examples

Input

4 3
0 1 W
1 2 W
5 3 B
5 4 B


Output

4


Input

2 1000
0 0 B
0 1 W


Output

2


Input

6 2
1 2 B
2 1 W
2 2 B
1 0 B
0 6 W
4 5 W


Output

4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Its Alice's birthday and her friend Bob gets him a birthday cake. Its nice delicious circle shaped cake of radius  R. Now they need to cut and eat that cake, so Alice fetches a cutter from her kitchen. It is a rectangular cutter of length A and breadth B that would knock of the part of the cake when the cutter is placed over it.

They decided to take turns to cut and eat their cake. Because it is Alice's birthday, she starts first. In each turn, they place the cutter over the cake, such that it is fully over the cake (i.e., no part of the cutter is outside the cake, or even over some previously cut region of the cake). You need to determine who will get more to eat, given both of them will use the optimal strategies.

Input and Output
The first line will contain the number of test cases T. Each of the next T lines will contain three space separated numbers R A B.

For each test case, you need to determine who will eat more. Print on a line "ALICE", "BOB" or "EQUAL" accordingly.

Constraints
1 ≤ T, R, A, B ≤ 1000

SAMPLE INPUT
2
1 2 2
1 1 1

SAMPLE OUTPUT
EQUAL
ALICE

Explanation
The cutter is bigger than the cake, hence nothing can be cut out.
Only one piece can be cut out from the cake. Hence Alice wins.

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