Ganesh Gaitonde has been convinced that he is Ashwathama ( invincible ). He now wants to do daring things in life. He is now using his own number system, Gaitonde System in Gopalmath. All the number in Gaitonde's system have 9 digits. In Gaitonde's system, he can change the priority of a digit.

Let's take an array A = [000000003,000000002,000000022,000000033]

Initially, the priority of digits are as follows: 0<1<2<3<4<5<6<7<8<9

sorted array B = [000000002,000000003,000000022,000000033]

after interchanging the priority of digits 2 and 3,

priority of digits: 0<1<3<2<4<5<6<7<8<9

sorted array B = [000000003,000000002,000000033,000000022]

after interchanging the priority of digits 0 and 9,

priority of digits: 9<1<3<2<4<5<6<7<8<0

sorted array B = [000000033,000000032,000000003,000000002]

 You are given two types of queries:

Type 0: 0 k - find the kth element of Array A if elements are sorted according to current priority of digits.

Type 1: 1 L R - Interchange the priority of digits L and R

Input Format : 

• The first line of input contains N and Q, the length of the Array A and Number of queries.
• The second line of input contains N elements each of length 9 digits of the array A.
•  Next, Q lines of input contain a query of the format described above.

Output Format :

• For each query of type 0, print kth element after sorting the array according to priority in new line.

Constraints :

• $1 \le N,Q \le 10^{5}$
• $1 \le K \le N$
• $0 \le L,R \le 9$