A keyword transposition cipher is a method of choosing a monoalphabetic substitution with which to encode a message. The substitution alphabet is determined by choosing a keyword, arranging the remaining letters of the alphabet in columns below the letters of the keyword, and then reading back the columns in the alphabetical order of the letters of the keyword.

For instance, if one chose the keyword SECRET, the columns generated would look like the following diagram. Note how the letters in the keyword are skipped when laying out the columns, and duplicate letters are removed from the keyword:

SECRT
ABDFG
HIJKL
MNOPQ
UVWXY
Z
Since the alphabetical order of the characters in the keyword is CERST, the columns are then read back in that order to get the substitution alphabet.

Original:     ABCDE FGHIJ KLMNO PQRSTU VWXYZ
Substitution: CDJOW EBINV RFKPX SAHMUZ TGLQY
Task

Given a piece of ciphertext and the keyword used to encipher it with the keyword transposition cipher described above, write an algorithm to output the original message.

Input Format

The first line of input will be an integer N indicating the number of test cases that will follow. For each test case in N, two additional lines will follow, one containing the keyword, and one containing the ciphertext. The keyword will be at most 7 characters long, and the ciphertext will be at most 255 characters in length.

Sample Input

2
SPORT
LDXTW KXDTL NBSFX BFOII LNBHG ODDWN BWK
SECRET
JHQSU XFXBQ
Output Format

Your output should be the decoded version of the cipher text for each test case, one per line.

Sample Output

ILOVE SOLVI NGPRO GRAMM INGCH ALLEN GES
CRYPT OLOGY
Given a triangle of numbers where each number is equal to the sum of the three numbers on top of it, find the first even number in a row.

Explanatory Note: The vertex of the triangle (at the top) is 1. The structure of the triangle is shown below. Each number is equal to the sum of the numbers at the following positions: Position X: immediately above it. Position Y: to the immediate left of X. Position Z: to the immediate right of X. If there are no numbers at positions X, Y, or Z, then assume those positions are occupied by a zero (0). This can occur for positions at the edge.

Here are four rows of the triangle:

          1
      1   1  1
   1  2   3  2  1
1  3  6   7  6  3  1
Input Format and Constraints
First line contains a number T (number of test cases).
Each of the next T lines contain a number N (the row number, assuming that the top vertex of the triangle is Row 1).

Output Format
For each test case, display an integer that denotes the position of the first even number.
Note: Assume that the left most number in a row is Position 1.
If there is no even number in a row, print -1.

Constraints
1<=T<=100
3<=N<=1000000000

Sample Input
2
3
4

Sample Output
2
3
Sorting is often useful as the first step in many different tasks. The most common task is to make finding things easier, but there are other uses also.

Challenge
Given a list of unsorted numbers, can you find the numbers that have the smallest absolute difference between them? If there are multiple pairs, find them all.

Input Format
There will be two lines of input:

n - the size of the list
array - the n numbers of the list
Output Format
Output the pairs of numbers with the smallest difference. If there are multiple pairs, output all of them in ascending order, all on the same line (consecutively) with just a single space between each pair of numbers. If there's a number which lies in two pair, print it two times (see sample case #3 for explanation).

Constraints
1 <= n <= 200000
-(107) <= x <= (107), where x ∈ array
array[i] != array[j], 0 <= i, j < N, and i != j

Sample Input #1

10
-20 -3916237 -357920 -3620601 7374819 -7330761 30 6246457 -6461594 266854
Sample Output #1

-20 30
Explanation
(30) - (-20) = 50, which is the smallest difference.
Numeros, The Artist, had two lists A and B, such that, B was a permutation of A. Numeros was very proud of these lists. Unfortunately, while transporting them from one exhibition to another, some numbers from List A got left out. Can you find out the numbers missing from A?

Notes

If a number occurs multiple times in the lists, you must ensure that the frequency of that number in both the lists is the same. If that is not the case, then it is also a missing number.
You have to print all the missing numbers in ascending order.
Print each missing number once, even if it is missing multiple times.
The difference between maximum and minimum number in the list B is less than or equal to 100.
Input Format
There will be four lines of input:

n - the size of the first list
This is followed by n space separated integers that make up the first list.
m - the size of the second list
This is followed by m space separated integers that make up the second list.

Output Format
Output the missing numbers in ascending order

Constraints
1<= n,m <= 1000010
1 <= x <= 10000 , x ∈ B
Xmax - Xmin < 101

Sample Input

10
203 204 205 206 207 208 203 204 205 206
13
203 204 204 205 206 207 205 208 203 206 205 206 204
Sample Output

204 205 206
Explanation
204 is present in both the arrays. Its frequency in A is 2, while its frequency in B is 3. Similarly, 205 and 206 occur twice in A, but thrice in B. So, these three numbers are our output. Rest of the numbers have same frequency in both the lists.
In the Quicksort challenges, you sorted an entire array. Sometimes, you just need specific information about a list of numbers, and doing a full sort would be unnecessary. Can you figure out a way to use your partition code to find the median in an array?

Challenge
Given a list of numbers, can you find the median?

Input Format
There will be two lines of input:

n - the size of the array
ar - n numbers that makes up the array
Output Format
Output one integer, the median.

Constraints
1<= n <= 1000001
-10000 <= x <= 10000 , x ∈ ar
There will be an odd number of elements.

Sample Input

7
0 1 2 4 6 5 3
Sample Output

3