Cho 2 số nguyên dương S và K. Một dãy số nguyên dương A = (A₁, A₂, …, A_n) được goi là một dãy số đẹp khi thỏa mãn 2 điều kiện:

• 1 <= A₁ < A₂ < … < A_n < S
• Với mỗi bộ số (x₁, x₂, …, x_n) nguyên không âm bất kỳ, A₁x₁ + A₂x₂ + … + A_nx_n khác S

Gọi A = (A₁, A₂, … , A_n) là dãy số đẹp có giá trị n lớn nhất với thứ tự từ điển nhỏ nhất, đưa ra giá trị A_K hoặc -1 nếu K > N

Cho T bộ test, hãy đưa ra kết quả của từng bộ test.

Giới hạn:

• T <= 1000
• 3 <= S <= 10¹⁸
• 1 <= K < S

Input:

Gồm T + 1 dòng

• Dòng 1 chứa số T, chỉ số bộ test
• • Dòng 2 đến T + 1, mỗi dòng chứa 2 số nguyên S và K

Output:

Gồm T dòng, mỗi dòng in ra kết quả của bộ test

Sample:

5  
3 1  
7 4  
10 3  
2022 507  
1000000000000000000 999999999999999999

Output:

2  
-1  
8  
1351  
-1

Subtask:

• Sub 1: S <= 500 (50%)
• Sub 2: Giới hạn mặc định của đề

Tại một trường bắn, một cung thủ thực hiện N phát bắn vào một mục tiêu có M vòng điểm.

Mục tiêu có thể được mô tả như sau

• Tâm của mục tiêu có tọa độ 0 (R₀ = 0).
• Với i = 0, 1, ..., M - 1, nếu mũi tên có khoảng cách so với tâm trong khoảng từ R_i đến R_i+1, cung thủ được S_i điểm.
• Nếu mũi tên có khoảng cách so với tâm lớn hơn S_M, cung thủ không được điểm
• Mũi tên bắn càng gần tâm, điểm càng cao (S₀ > S₁ > ... > S_M)

Một luật đặc biệt được áp dụng: 2 mũi tên bất kỳ phải cách nhau ít nhất D

Tìm số điểm lớn nhất mà cung thủ có thể đạt được

Giới hạn:

• 1 <= N, M <= 10⁵
• 1 <= D <= 10⁶
• 0 = R₀ < R₁ < ... < R_M < 10¹¹
• 10¹¹ >= S₀ > ... > S_M-1 > 0
• Tất cả số liệu đều là số nguyên

Input: Gồm 3 dòng

• Dòng 1: Gồm 3 số N, M, D
• Dòng 2: Gồm M + 1 số R₀, R₁, ..., R_M
• Dòng 3: Gồm M số S₀, S₁, ..., S_M-1

Output:

Gồm 1 dòng là kết quả bài toán

Sample:

3 3 3
0 2 5 6
90 60 30

Output:

240

Subtask:

• Sub 1: 1 <= N, M, D <= 100 (25%)
• Sub 2: 1 <= M, D <= 1000 (25%)
• Sub 3: Giới hạn mặc định (50%)

Mã hóa này được mô tả bởi hai chuỗi ~A~ và ~B~ , trong đó mỗi ký tự ở chuỗi ~A~ được ánh xạ tới một ký tự tương ứng trong chuỗi ~B~ . Ví dụ, nếu:

• ~A~ = abcdefghijklmnopqrstuvwxyz
• ~B~ = zyxwvutsrqponmlkjihgfedcba
• thì a sẽ được ánh xạ thành z, b sẽ thành y, ....

Nhưng nếu chỉ mã hóa 1 lần thì quá dễ đoán, nên việc mã hóa được lặp lại ~N~ lần. Hãy đưa ra xâu ~S~ sau khi được mã hóa ~N~ lần

Input

Dòng 1: xâu S gồm toàn ký tự latin in thường

Dòng thứ 2 chứa 1 số nguyên ~N~

2 dòng tiếp theo chứa 2 xâu ~A~ và ~B~ là hoán vị của bảng chữ cái latin tiếng Anh chỉ mã hóa của đề bài

Output

Một xâu là mã hóa của ~S~ sau ~N~ lần

Giới hạn

• Sub 1: ~N~ = 1
• Sub 2: ~N, |S| <= 2000~
• Sub 3: ~N <= 10^5~
• Sub 4: ~N <= 10^9, |S| <= 10^5~

Test mẫu

Input

hnoi
2
abcdefghijklmnopqrstuvwxyz
pnudzgabijkyehlrqxfmsctovw

Output

nbyi