TSEC Round 1 (Div. 4)
A. Who Hates Abhishek?
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

A permutation is a list of integers $$$a_1, a_2, \cdots, a_n$$$, consisting of $$$n$$$ distinct non-negative and non-zero integers, each of them doesn't exceed $$$n$$$.

Abhishek hates permutations. But he hates some permutations more than the others. He calls such permutations wahiyat. A wahiyat permutation is such permutation $$$a$$$ that for any $$$j$$$ $$$(1 \le j \le n)$$$ the following equations hold $$$a_{a_j} = j$$$ and $$$a_j \neq j$$$. Since you don't like what Abhishek and want to annoy him more so you need to find any permutation that is wahiyat permutation.

Input

A single line contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the permutation size.

Output

If a wahiyat permutation of size $$$n$$$ doesn't exist, print a single integer -1. Otherwise print $$$n$$$ distinct integers from 1 to $$$n$$$, $$$a_1, a_2, \cdots, a_n$$$ — permutation $$$a$$$

Examples
Input
6
Output
2 1 4 3 6 5
Input
4
Output
2 1 4 3

B1. Xor Pairs (Easy Version)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array of $$$n$$$ integers (a1, a2, a3, ....... an)

You have to find the number of pairs such that a[i] xor a[j] = a[i]

Input

First line has a single integer $$$t$$$, number of tests [1 <= $$$t$$$ <= 10]

First line of each test has a single integer $$$n$$$, size of array [1 <= $$$n$$$ <= 100]

Second line of each test has $$$n$$$ integers, the array elements [0 <= $$$a[i]$$$ <= 1e9]

It is guaranteed that sum of n among all tests do not exceed 100

Output

For each test, print a single integer, the number of pairs

Example
Input
3
5
0 1 0 2 0
7
0 1 1 2 3 0 1
4
0 0 0 0
Output
15
14
16

B2. Xor Pairs (Hard Version)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The difference between easy and hard version are the constraints on n

You are given an array of $$$n$$$ integers (a1, a2, a3, ....... an)

You have to find the number of pairs such that a[i] xor a[j] = a[i]

Input

First line has a single integer $$$t$$$, number of tests [1 <= $$$t$$$ <= 1000]

First line of each test has a single integer $$$n$$$, size of array [1 <= $$$n$$$ <= 1e5]

Second line of each test has $$$n$$$ integers, the array elements [0 <= $$$a[i]$$$ <= 1e9]

It is guaranteed that sum of n among all tests do not exceed 1e5

Output

For each test, print a single integer, the number of pairs

Example
Input
3
5
0 1 0 2 0
7
0 1 1 2 3 0 1
4
0 0 0 0
Output
15
14
16

C. Dhrumil The Pados Wali Aunty
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Dhrumil was once very bored because he was missing the choas and fight. Yeah, he doesn't like when everything is going well :)

To spice things up he decided to spark a debate between his friends based on Which is better. Is it Marvel? or Is it DC?

So he brought his $$$2n$$$ friends, the $$$i$$$-th member has fighting level $$$a_i$$$. He then assigned each of his friend to one of the two Teams (Marvel or DC). Remember each team can only have odd number of members. The number of members in the 2 Teams may be equal or different. Every member has to be assigned to exactly one class.

Let's define fighting level of a Team as the median of fighting levels of the members in the team.

Reminder: median

To make things more fun he want's to minimize the absolute difference between the fighting levels of the 2 Teams (Better script writer than Jay Shah......)

You as Dhrumil, have to find among such partitions, What is the minimum possible absolute difference you can achieve between fighting levels of two teams of odd sizes?

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the number of members/2.

The second line of each test case contains $$$2n$$$ integers $$$a_1, a_2, \dots, a_{2 n}$$$ ($$$1 \le a_i \le 10^9$$$) — fighting levels of members.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output

For each test case, output a single integer, the minimum possible absolute difference between fighting levels of two teams of odd sizes.

Example
Input
3
4
2 5 8 1 10 10 5 2
4
8 2 4 10 5 6 9 10
4
1 5 9 8 8 8 6 5
Output
0
2
2

D. Make It Good
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$a$$$ consisting of $$$n$$$ integers. You have to find the length of the longest prefix of elements which is a good array.

The array $$$b$$$ of length $$$m$$$ is called good, if you can obtain a non-decreasing array $$$c$$$ ($$$c_1 \le c_2 \le \dots \le c_{m}$$$) from it, repeating the following operation $$$m$$$ times (initially, $$$c$$$ is empty):

  • select either the first or the last element of $$$b$$$, remove it from $$$b$$$, and append it to the end of the array $$$c$$$.

For example, if we do $$$4$$$ operations: take $$$b_1$$$, then $$$b_{m}$$$, then $$$b_{m-1}$$$ and at last $$$b_2$$$, then $$$b$$$ becomes $$$[b_3, b_4, \dots, b_{m-3}]$$$ and $$$c =[b_1, b_{m}, b_{m-1}, b_2]$$$.

Consider the following example: $$$b = [1, 2, 3, 4, 4, 2, 1]$$$. This array is good because we can obtain non-decreasing array $$$c$$$ from it by the following sequence of operations:

  1. take the first element of $$$b$$$, so $$$b = [2, 3, 4, 4, 2, 1]$$$, $$$c = [1]$$$;
  2. take the last element of $$$b$$$, so $$$b = [2, 3, 4, 4, 2]$$$, $$$c = [1, 1]$$$;
  3. take the last element of $$$b$$$, so $$$b = [2, 3, 4, 4]$$$, $$$c = [1, 1, 2]$$$;
  4. take the first element of $$$b$$$, so $$$b = [3, 4, 4]$$$, $$$c = [1, 1, 2, 2]$$$;
  5. take the first element of $$$b$$$, so $$$b = [4, 4]$$$, $$$c = [1, 1, 2, 2, 3]$$$;
  6. take the last element of $$$b$$$, so $$$b = [4]$$$, $$$c = [1, 1, 2, 2, 3, 4]$$$;
  7. take the only element of $$$b$$$, so $$$b = []$$$, $$$c = [1, 1, 2, 2, 3, 4, 4]$$$ — $$$c$$$ is non-decreasing.

Note that the array consisting of one element is good.

Print the length of the longest prefix of $$$a$$$, which is a good array.

Input

The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. Then $$$t$$$ test cases follow.

The first line of the test case contains one integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the length of $$$a$$$. The second line of the test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$), where $$$a_i$$$ is the $$$i$$$-th element of $$$a$$$.

It is guaranteed that the sum of $$$n$$$ among all tests does not exceed $$$10^5$$$

Output

For each test case, print the length of the longest prefix of $$$a$$$, which is a good array.

Example
Input
5
4
1 2 3 4
7
4 3 3 8 4 5 2
3
1 1 1
7
1 3 1 4 5 3 2
5
5 4 3 2 3
Output
4
3
3
3
4
Note

In the first test case of the example, the array $$$a$$$ is already good

In the second test case of the example, the initial array $$$a$$$ is not good. Let's erase last $$$4$$$ elements of $$$a$$$, the result is $$$[4, 3, 3]$$$. The resulting array is goodest prefix

E. String Palindrome Game
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are playing the String Palindrome Game, you are given a string of length $$$n$$$ and $$$q$$$ levels to play.

In each level, you are given $$$l$$$ and $$$r$$$.

If you can find a palindrome between $$$s[l], s[l+1], s[l+2].... s[r]$$$, the points you get = length of palindrome found

It is not necessary that your palindrome needs to start with $$$s[l]$$$ and ends with $$$s[r]$$$, it can be any substring from $$$[l, r]$$$ inclusive

For each level, find the maximum score u can obtain

Example : $$$s = abcddbca$$$ and $$$[l, r] = [1, 6]$$$, so your substring is $$$abcddb$$$, the longest palindrome is $$$dd$$$, so u get $$$2$$$ points

Input

First line of input consists of a single integer $$$t$$$, number of testcases [1 <= $$$t$$$ <= 100]

First line of each test consists of two integers, $$$n$$$ and $$$q$$$ [1 <= $$$n, q$$$ <= 1000]

Second line of each test consists of the string.

Then n lines follow, containing the queries

It is guaranteed that sum of $$$n * q$$$ among all tests do not exceed $$$10^6$$$

Output

For each query, print the maximum number of points you can get

Example
Input
2
8 5
abcddcba
1 8
2 7
2 8
4 4
3 6
5 3
aaabb
1 5
4 5
2 3
Output
8
6
6
1
4
3
2
2

F. Inversion Sum
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

An Inversion is a pair of indexes $$$(i, j)$$$ such that $$$i \lt j$$$ and $$$a[i] \gt a[j]$$$

Example : [3, 2, 1] has 3 inversions => indexes (1, 2), (1, 3) and (2, 3)

You need to find the sum of inversions of all possible permutations of length n

=> An identity permutation = [1, 2, 3, 4, ..... n]

Input

First line consists of a single integer t, number of testcases [1 <= $$$t$$$ <= $$$10^6$$$]

First line of each test consists of a single integer n, size of permutation [1 <= $$$n$$$ <= $$$10^6$$$]

Output

For each test, print a single integer, the sum of inversions of all possible permutations

Example
Input
4
1
2
3
4
Output
0
1
9
72
Note

For n = 3

[1, 2, 3] = 0 inversions

[1, 3, 2] = 1 inversion

[2, 1, 3] = 1 inversion

[2, 3, 1] = 2 inversions

[3, 1, 2] = 2 inversions

[3, 2, 1] = 3 inversions