vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
You are given a rooted tree with root in vertex 1. Each vertex is coloured in some colour.

Let's call colour c dominating in the subtree of vertex v if there are no other colours that appear in the subtree of vertex v more times than colour c. So it's possible that two or more colours will be dominating in the subtree of some vertex.

The subtree of vertex v is the vertex v and all other vertices that contains vertex v in each path to the root.

For each vertex v find the sum of all dominating colours in the subtree of vertex v.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 10^5) — the number of vertices in the tree.

The second line contains n integers c_{i} (1 ≤ c_{i} ≤ n), c_{i} — the colour of the i-th vertex.

Each of the next n - 1 lines contains two integers x_{j}, y_{j} (1 ≤ x_{j}, y_{j} ≤ n) — the edge of the tree. The first vertex is the root of the tree.


-----Output-----

Print n integers — the sums of dominating colours for each vertex.


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

Output
10 9 3 4

Input
15
1 2 3 1 2 3 3 1 1 3 2 2 1 2 3
1 2
1 3
1 4
1 14
1 15
2 5
2 6
2 7
3 8
3 9
3 10
4 11
4 12
4 13

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

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
For every good kata idea there seem to be quite a few bad ones!

In this kata you need to check the provided 2 dimensional array (x) for good ideas 'good' and bad ideas 'bad'. If there are one or two good ideas, return 'Publish!', if there are more than 2 return 'I smell a series!'. If there are no good ideas, as is often the case, return 'Fail!'.

The sub arrays may not be the same length.

The solution should be case insensitive (ie good, GOOD and gOOd all count as a good idea). All inputs may not be strings.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given is a string S of length N.
Find the maximum length of a non-empty string that occurs twice or more in S as contiguous substrings without overlapping.
More formally, find the maximum positive integer len such that there exist integers l_1 and l_2 ( 1 \leq l_1, l_2 \leq N - len + 1 ) that satisfy the following:
 - l_1 + len \leq l_2
 - S[l_1+i] = S[l_2+i] (i = 0, 1, ..., len - 1)
If there is no such integer len, print 0.

-----Constraints-----
 - 2 \leq N \leq 5 \times 10^3
 - |S| = N
 - S consists of lowercase English letters.

-----Input-----
Input is given from Standard Input in the following format:
N
S

-----Output-----
Print the maximum length of a non-empty string that occurs twice or more in S as contiguous substrings without overlapping. If there is no such non-empty string, print 0 instead.

-----Sample Input-----
5
ababa

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

The strings satisfying the conditions are: a, b, ab, and ba. The maximum length among them is 2, which is the answer.
Note that aba occurs twice in S as contiguous substrings, but there is no pair of integers l_1 and l_2 mentioned in the statement such that l_1 + len \leq l_2.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
A two dimensional array is called a bracket array if each grid contains one of the two possible brackets — "(" or ")". A path through the two dimensional array cells is called monotonous if any two consecutive cells in the path are side-adjacent and each cell of the path is located below or to the right from the previous one. 

A two dimensional array whose size equals *n*<=×<=*m* is called a correct bracket array, if any string formed by writing out the brackets on some monotonous way from cell (1,<=1) to cell (*n*,<=*m*) forms a correct bracket sequence. 

Let's define the operation of comparing two correct bracket arrays of equal size (*a* and *b*) like that. Let's consider a given two dimensional array of priorities (*c*) — a two dimensional array of same size, containing different integers from 1 to *nm*. Let's find such position (*i*,<=*j*) in the two dimensional array, that *a**i*,<=*j*<=≠<=*b**i*,<=*j*. If there are several such positions, let's choose the one where number *c**i*,<=*j* is minimum. If *a**i*,<=*j*<==<="(", then *a*<=&lt;<=*b*, otherwise *a*<=&gt;<=*b*. If the position (*i*,<=*j*) is not found, then the arrays are considered equal.

Your task is to find a *k*-th two dimensional correct bracket array. It is guaranteed that for the given sizes of *n* and *m* there will be no less than *k* two dimensional correct bracket arrays.

Input Specification:
The first line contains integers *n*, *m* and *k* — the sizes of the array and the number of the sought correct bracket array (1<=≤<=*n*,<=*m*<=≤<=100, 1<=≤<=*k*<=≤<=1018). Then an array of priorities is given, *n* lines each containing *m* numbers, number *p**i*,<=*j* shows the priority of character *j* in line *i* (1<=≤<=*p**i*,<=*j*<=≤<=*nm*, all *p**i*,<=*j* are different).

Please do not use the %lld specificator to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specificator.

Output Specification:
Print the *k*-th two dimensional correct bracket array.

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

Demo Output:
['()\n', '(()\n())\n', '()\n)(\n()\n']

Note:
In the first sample exists only one correct two-dimensional bracket array.

In the second and in the third samples two arrays exist.

A bracket sequence is called regular if it is possible to obtain correct arithmetic expression by inserting characters «+» and «1» into this sequence. For example, sequences «(())()», «()» and «(()(()))» are regular, while «)(», «(()» and «(()))(» are not.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Rani has challenged Nandu to generate Splendid Matrices. Splendid matrices are square matrices with dimensions 2^n X 2^n filled in a particular manner. To explain this manner, Rani gives Nandu the matrices for n=1, n=2 and n=3 : 

n=1
1 2
3 4

n=2 (spacing for clarity)
1  2  5  6
3  4  7  8
9  10 13 14
11 12 15 16

n=3 (spacing for clarity)
1  2  5  6  17 18 21 22 
3  4  7  8  19 20 23 24 
9  10 13 14 25 26 29 30 
11 12 15 16 27 28 31 32 
33 34 37 38 49 50 53 54 
35 36 39 40 51 52 55 56 
41 42 45 46 57 58 61 62 
43 44 47 48 59 60 63 64

Given n, please help Nandu in generating the Splendid Matrix with dimensions 2^n X 2^n.
Input
A single line consisting of n.
Output
n lines. Each line should consist of n integers separated by single spaces.
Constraints
1 < = n < = 10

SAMPLE INPUT
3

SAMPLE OUTPUT
1 2 5 6 17 18 21 22 
3 4 7 8 19 20 23 24 
9 10 13 14 25 26 29 30 
11 12 15 16 27 28 31 32 
33 34 37 38 49 50 53 54 
35 36 39 40 51 52 55 56 
41 42 45 46 57 58 61 62 
43 44 47 48 59 60 63 64

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Aryo has got a lot of intervals for his 2418th birthday. He is really excited and decided to color all these intervals with some colors. He has a simple rule for himself. He calls a coloring nice if there exists no three intervals a, b and c such that the following conditions are satisfied simultaneously: 

  * a, b and c are colored with the same color, 
  * <image>, 
  * <image>, 
  * <image>. 



Moreover he found out that for every intervals i and j, there is at least one point in i which isn't in j.

Given some set of intervals. You have to find the minimum number k, such that Aryo can find a nice coloring with k colors.

Input

The first line contains a single integer n (1 ≤ n ≤ 103), number of intervals.

The following n lines contain a interval description each. Each interval is described by two numbers si, ei which are the start and end points of it ( - 105 < si, ei < 105, si ≤ ei). See samples for clarity. A square bracket stands for including of the corresponding endpoint, while a round bracket stands for excluding.

Output

Write a single integer k — the minimum number of colors needed for a nice coloring.

Examples

Input

2
[1,2)
(3,4]


Output

1


Input

3
[1,3]
[2,6]
(5,7)


Output

2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Two integer sequences existed initially — one of them was strictly increasing, and the other one — strictly decreasing.

Strictly increasing sequence is a sequence of integers $[x_1 < x_2 < \dots < x_k]$. And strictly decreasing sequence is a sequence of integers $[y_1 > y_2 > \dots > y_l]$. Note that the empty sequence and the sequence consisting of one element can be considered as increasing or decreasing.

They were merged into one sequence $a$. After that sequence $a$ got shuffled. For example, some of the possible resulting sequences $a$ for an increasing sequence $[1, 3, 4]$ and a decreasing sequence $[10, 4, 2]$ are sequences $[1, 2, 3, 4, 4, 10]$ or $[4, 2, 1, 10, 4, 3]$.

This shuffled sequence $a$ is given in the input.

Your task is to find any two suitable initial sequences. One of them should be strictly increasing and the other one — strictly decreasing. Note that the empty sequence and the sequence consisting of one element can be considered as increasing or decreasing.

If there is a contradiction in the input and it is impossible to split the given sequence $a$ to increasing and decreasing sequences, print "NO".


-----Input-----

The first line of the input contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of elements in $a$.

The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 2 \cdot 10^5$), where $a_i$ is the $i$-th element of $a$.


-----Output-----

If there is a contradiction in the input and it is impossible to split the given sequence $a$ to increasing and decreasing sequences, print "NO" in the first line.

Otherwise print "YES" in the first line and any two suitable sequences. Note that the empty sequence and the sequence consisting of one element can be considered as increasing or decreasing.

In the second line print $n_i$ — the number of elements in the strictly increasing sequence. $n_i$ can be zero, in this case the increasing sequence is empty.

In the third line print $n_i$ integers $inc_1, inc_2, \dots, inc_{n_i}$ in the increasing order of its values ($inc_1 < inc_2 < \dots < inc_{n_i}$) — the strictly increasing sequence itself. You can keep this line empty if $n_i = 0$ (or just print the empty line).

In the fourth line print $n_d$ — the number of elements in the strictly decreasing sequence. $n_d$ can be zero, in this case the decreasing sequence is empty.

In the fifth line print $n_d$ integers $dec_1, dec_2, \dots, dec_{n_d}$ in the decreasing order of its values ($dec_1 > dec_2 > \dots > dec_{n_d}$) — the strictly decreasing sequence itself. You can keep this line empty if $n_d = 0$ (or just print the empty line).

$n_i + n_d$ should be equal to $n$ and the union of printed sequences should be a permutation of the given sequence (in case of "YES" answer).


-----Examples-----
Input
7
7 2 7 3 3 1 4

Output
YES
2
3 7 
5
7 4 3 2 1 

Input
5
4 3 1 5 3

Output
YES
1
3 
4
5 4 3 1 

Input
5
1 1 2 1 2

Output
NO

Input
5
0 1 2 3 4

Output
YES
0

5
4 3 2 1 0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.

Example:

nums = [1, 2, 3]
target = 4

The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

Note that different sequences are counted as different combinations.

Therefore the output is 7.



Follow up:
What if negative numbers are allowed in the given array?
How does it change the problem?
What limitation we need to add to the question to allow negative numbers? 

Credits:Special thanks to @pbrother for adding this problem and creating all test cases.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
After too much playing on paper, Iahub has switched to computer games. The game he plays is called "Block Towers". It is played in a rectangular grid with n rows and m columns (it contains n × m cells). The goal of the game is to build your own city. Some cells in the grid are big holes, where Iahub can't build any building. The rest of cells are empty. In some empty cell Iahub can build exactly one tower of two following types:

  1. Blue towers. Each has population limit equal to 100. 
  2. Red towers. Each has population limit equal to 200. However, it can be built in some cell only if in that moment at least one of the neighbouring cells has a Blue Tower. Two cells are neighbours is they share a side. 



Iahub is also allowed to destroy a building from any cell. He can do this operation as much as he wants. After destroying a building, the other buildings are not influenced, and the destroyed cell becomes empty (so Iahub can build a tower in this cell if needed, see the second example for such a case).

Iahub can convince as many population as he wants to come into his city. So he needs to configure his city to allow maximum population possible. Therefore he should find a sequence of operations that builds the city in an optimal way, so that total population limit is as large as possible.

He says he's the best at this game, but he doesn't have the optimal solution. Write a program that calculates the optimal one, to show him that he's not as good as he thinks. 

Input

The first line of the input contains two integers n and m (1 ≤ n, m ≤ 500). Each of the next n lines contains m characters, describing the grid. The j-th character in the i-th line is '.' if you're allowed to build at the cell with coordinates (i, j) a tower (empty cell) or '#' if there is a big hole there. 

Output

Print an integer k in the first line (0 ≤ k ≤ 106) — the number of operations Iahub should perform to obtain optimal result.

Each of the following k lines must contain a single operation in the following format:

  1. «B x y» (1 ≤ x ≤ n, 1 ≤ y ≤ m) — building a blue tower at the cell (x, y); 
  2. «R x y» (1 ≤ x ≤ n, 1 ≤ y ≤ m) — building a red tower at the cell (x, y); 
  3. «D x y» (1 ≤ x ≤ n, 1 ≤ y ≤ m) — destroying a tower at the cell (x, y). 



If there are multiple solutions you can output any of them. Note, that you shouldn't minimize the number of operations.

Examples

Input

2 3
..#
.#.


Output

4
B 1 1
R 1 2
R 2 1
B 2 3


Input

1 3
...


Output

5
B 1 1
B 1 2
R 1 3
D 1 2
R 1 2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an array a consisting of n integers.

In one move, you can choose some index i (1 ≤ i ≤ n - 2) and shift the segment [a_i, a_{i + 1}, a_{i + 2}] cyclically to the right (i.e. replace the segment [a_i, a_{i + 1}, a_{i + 2}] with [a_{i + 2}, a_i, a_{i + 1}]). 

Your task is to sort the initial array by no more than n^2 such operations or say that it is impossible to do that.

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 (3 ≤ n ≤ 500) — the length of a. The second line of the test case contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 500), where a_i is the i-th element a.

It is guaranteed that the sum of n does not exceed 500.

Output

For each test case, print the answer: -1 on the only line if it is impossible to sort the given array using operations described in the problem statement, or the number of operations ans on the first line and ans integers idx_1, idx_2, ..., idx_{ans} (1 ≤ idx_i ≤ n - 2), where idx_i is the index of left border of the segment for the i-th operation. You should print indices in order of performing operations.

Example

Input


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


Output


0

6
3 1 3 2 2 3 
13
2 1 1 6 4 2 4 3 3 4 4 6 6 
-1
4
3 3 4 4 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have an infinite number of 4 types of lego blocks of sizes given as (depth x height x width):

d	h	w
1	1	1
1	1	2
1	1	3
1	1	4

Using these blocks, you want to make a wall of height $n$ and width $m$. Features of the wall are: 

- The wall should not have any holes in it. 

- The wall you build should be one solid structure, so there should not be a straight vertical break across all rows of bricks. 

- The bricks must be laid horizontally.   

How many ways can the wall be built?

Example  

$n=2$ 

$m=3$  

The height is $2$ and the width is $3$.  Here are some configurations:  

These are not all of the valid permutations.  There are $\mbox{9}$ valid permutations in all.  

Function Description  

Complete the legoBlocks function in the editor below.  

legoBlocks has the following parameter(s):

int n: the height of the wall  
int m: the width of the wall   

Returns 

- int: the number of valid wall formations modulo $(10^9+7)$  

Input Format

The first line contains the number of test cases $\boldsymbol{\boldsymbol{t}}$.  

Each of the next $\boldsymbol{\boldsymbol{t}}$ lines contains two space-separated integers $n$ and $m$.  

Constraints

$1\leq t\leq100$ 

$1\leq n,m\leq1000$  

Sample Input
STDIN   Function
-----   --------
4       t = 4
2 2     n = 2, m = 2
3 2     n = 3, m = 2
2 3     n = 2, m = 3
4 4     n = 4, m = 4

Sample Output
3  
7  
9  
3375

Explanation

For the first case, we can have:  

$3\:\:\:\text{mod}\:(10^9+7)=3$  

For the second case, each row of the wall can contain either two blocks of width 1, or one block of width 2. However, the wall where all rows contain two blocks of width 1 is not a solid one as it can be divided vertically. Thus, the number of ways is $2\times2\times2-1=7$ and $7\:\:\:\text{mod}\:(10^9+7)=7$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A flower shop has got n bouquets, and the i-th bouquet consists of a_{i} flowers. Vasya, the manager of the shop, decided to make large bouquets from these bouquets. 

Vasya thinks that a bouquet is large if it is made of two or more initial bouquets, and there is a constraint: the total number of flowers in a large bouquet should be odd. Each of the initial bouquets can be a part of at most one large bouquet. If an initial bouquet becomes a part of a large bouquet, all its flowers are included in the large bouquet.

Determine the maximum possible number of large bouquets Vasya can make. 


-----Input-----

The first line contains a single positive integer n (1 ≤ n ≤ 10^5) — the number of initial bouquets.

The second line contains a sequence of integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^6) — the number of flowers in each of the initial bouquets.


-----Output-----

Print the maximum number of large bouquets Vasya can make. 


-----Examples-----
Input
5
2 3 4 2 7

Output
2

Input
6
2 2 6 8 6 12

Output
0

Input
3
11 4 10

Output
1



-----Note-----

In the first example Vasya can make 2 large bouquets. For example, the first bouquet can contain the first and the fifth initial bouquets (the total number of flowers is then equal to 9), and the second bouquet can consist of the second and the third initial bouquets (the total number of flowers is then equal to 7). The fourth initial bouquet is unused in this scheme. 

In the second example it is not possible to form a single bouquet with odd number of flowers.

In the third example Vasya can make one large bouquet. For example, he can make it using all three initial bouquets. The size of the large bouquet is then equal to 11 + 4 + 10 = 25.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Getting a business permit in Kafkatown requires a trip to City Hall. There you are given a permit form that must be signed by $K$ city clerks whose names are printed at the bottom of the form.

Entering the clerks’ room, you find a long line of people working their way down a narrow aisle along the clerks’ desks. Their desks are arranged in increasing numeric order. The aisle is so narrow that the line is forced to shuffle forward, single file, past each of the clerks’ desk in turn. Once in the line you cannot leave, back up, or change positions with other people.

As you present your permit for a signature, you are told that no clerk will sign unless all of the signatures above his or her name on the permit form have already been filled in. To your dismay, the clerks’ desks are not arranged in the same order as the names on your form.

How many times do you need to pass through the line until you can get your permit?

-----Input-----
The first line of input contains an integer $K$, the number of signatures you need to collect ($1 \leq K \leq 100$).

This is followed by $K$ lines of input, each containing an integer in the range $1\ldots 100$, indicating the desk numbers of each of the clerks whose signature you need, in the order that they appear on your form. (Clerks whose signatures are not needed on your form are omitted from this list.)

For example, the input

    5 1 23 18 13 99

means that you need $5$ signatures. The first must come from the clerk in desk #$1$, the next from the clerk in desk #$23$, and so on, with the final signature coming from the clerk in desk #$99$.

No desk number appears more than once in the input.

-----Output-----
Print a single line containing an integer denoting the number of passes you need to make through the line until you can collect the signatures that you need.

-----Examples-----
Sample Input 1:
5
1
23
18
13
99
Sample Output 1:
3

Sample Input 2:
5
11
20
33
40
55
Sample Output 2:
1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
### Count the number of Duplicates

Write a function that will return the count of **distinct case-insensitive** alphabetic characters and numeric digits that occur more than 
once in the input string. 
The input string can be assumed to contain only alphabets (both uppercase and lowercase) and numeric digits.


### Example
"abcde" -> 0             `# no characters repeats more than once`  
"aabbcde" -> 2           `# 'a' and 'b'`  
"aabBcde" -> 2           ``# 'a' occurs twice and 'b' twice (`b` and `B`)``  
"indivisibility" -> 1    `# 'i' occurs six times`  
"Indivisibilities" -> 2  `# 'i' occurs seven times and 's' occurs twice`  
"aA11" -> 2              `# 'a' and '1'`  
"ABBA" -> 2              `# 'A' and 'B' each occur twice`

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
A string $s$ of length $n$ can be encrypted by the following algorithm:
 -  iterate over all divisors of $n$ in decreasing order (i.e. from $n$ to $1$), -  for each divisor $d$, reverse the substring $s[1 \dots d]$ (i.e. the substring which starts at position $1$ and ends at position $d$). 
For example, the above algorithm applied to the string $s$="codeforces" leads to the following changes: "codeforces" $\to$ "secrofedoc" $\to$ "orcesfedoc" $\to$ "rocesfedoc" $\to$ "rocesfedoc" (obviously, the last reverse operation doesn't change the string because $d=1$).

You are given the encrypted string $t$. Your task is to decrypt this string, i.e., to find a string $s$ such that the above algorithm results in string $t$. It can be proven that this string $s$ always exists and is unique.

Input Specification:
The first line of input consists of a single integer $n$ ($1 \le n \le 100$) — the length of the string $t$. The second line of input consists of the string $t$. The length of $t$ is $n$, and it consists only of lowercase Latin letters.

Output Specification:
Print a string $s$ such that the above algorithm results in $t$.

Demo Input:
['10\nrocesfedoc\n', '16\nplmaetwoxesisiht\n', '1\nz\n']

Demo Output:
['codeforces\n', 'thisisexampletwo\n', 'z\n']

Note:
The first example is described in the problem statement.

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