Tuấn có một chuỗi ký tự chỉ gồm các chữ cái thường tiếng Anh và đang cố mã hóa chuỗi này theo một mã hóa nhất định.

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 được ánh xạ thành z và b được ánh xạ thành y, ...

Việc biến đổi chuỗi chỉ một lần thì khá nhàm chán, vì vậy, với một số nguyên dương K, Tuấn muốn lặp lại quá trình mã hóa này K lần. Nhưng giờ đây Tuấn đã mệt và nhờ bạn giúp đỡ. Bạn có thể giúp Tuấn để có được chuỗi cuối cùng không?

Đầu vào:

Dòng đầu tiên chứa xâu S (1 <= |S| <= 10^5) chỉ gồm các kí tự La-tinh in thường.

Dòng tiếp theo chứa một số nguyên dương K (1 <= K <= 10^9).

Hai dòng tiếp theo, mỗi dòng chứa lần lượt hai xâu A và B có đúng 26 kí tự là hoán vị của các kí tự La-tinh in thường từ a đến z.

Đầu ra: In ra một xâu duy nhất là kết quả bài toán.

Input:

hnoi
2
abcdefghijklmnopqrstuvwxyz
pnudzgabijkyehlrqxfmsctovw

Output:

nbyi

Giải thích: Các ký tự hnoi được mã hóa như sau:

h → b → n

n → h → b

o → l → y

i → i → i

Số trùng là một số tự nhiên mà chữ số đầu tiên trùng với chữ số cuối cùng. Ví dụ: 8, 66, 686, 8398, ...

Nhập vào một số tự nhiên N. Hãy đếm xem có bao nhiêu số trùng nhỏ hơn N.

Ví dụ: N = 124, có các số thoả mãn: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, 44, 55, 66, 77, 88, 99, 101, 111, 121. Vậy có 22 số thỏa mãn.

Input: Số tự nhiên N (N ≤ 10^9).

Output: Một số nguyên duy nhất là kết quả của bài toán.

Sample Test

Input:

124

Output:

22

Cho chuỗi S và chuỗi P chỉ chứa ký tự chữ thường. Gọi K là độ dài của P.

Hãy đếm xem trong S có bao nhiêu chuỗi con độ dài K là hoán vị của P (chứa các ký tự giống P, không quan trọng thứ tự).

Input:

• Dòng 1: Chuỗi S.

• Dòng 2: Chuỗi P.

Output:

• Số lượng chuỗi con thỏa mãn.

Ví dụ 1:

Input:

cbaebabacd
abc

Output:

2

Ví dụ 2:

Input:

abab
ab

Output:

3

Cho mảng A gồm N số nguyên (có thể âm). Hãy tìm đoạn con liên tiếp (ít nhất 1 phần tử) có tổng lớn nhất.

Dữ liệu vào:

Dòng 1: Số nguyên N (1 <= N <= 10^5).

Dòng 2: N số nguyên A[i] (|A[i]| <= 10^9).

Dữ liệu ra:

Tổng lớn nhất của đoạn con liên tiếp.

Ví dụ:

Input:

8 
-2 -3 4 -1 -2 1 5 -3

Output:

7