Một số nguyên tố là số tự nhiên lớn hơn ~1~ có ~2~ ước dương là ~1~ và chính nó. Một số ~n~ được gọi là số song nguyên tố nếu ~n~ là số nguyên tố và tổng các chữ số của số ~n~ cũng là số nguyên tố. Ví dụ số ~23~ là số song nguyên tố vì ~23~ là số nguyên tố và tổng các chữ số của số ~23~ bằng ~5~ cũng là số nguyên tố.

Yêu cầu: Cho 2 số nguyên ~L~ và ~R~ với ~1 < L ≤ R ≤ 10^{6}~, hãy tính số lượng các số song nguyên tố thuộc đoạn ~[L, R]~.

INPUT

Gồm một dòng chứa hai số nguyên ~L~ và ~R~, mỗi số cách nhau một dấu cách.

OUTPUT

Gồm một dòng là số lượng các số song nguyên tố thuộc đoạn ~[L, R]~. Nếu các giá trị của ~L~ và ~R~ không thỏa mãn điều kiện bài toán thì ghi là ~-1~.

SUBTASKS

• ~10 \%~ số test ứng với các giá trị của ~L~ và ~R~ không thỏa mãn điều kiện bài toán;
• ~70 \%~ số test ứng với ~1 < L ≤ R ≤ 10^{4}~;
• ~20 \%~ số test ứng với ~1 < L ≤ R ≤ 10^{6}~.

SAMPLE INPUT

10 30

SAMPLE OUTPUT

3

Cho hai dãy số nguyên ~a_1, a_2, ..., a_n~ và ~b_1, b_2, ..., b_n~ với điều kiện ~1 < n ≤ 5 \times 10^{4}~ và ~1 ≤ a_i, b_i ≤ 10^{9}~.

Hai dãy số ~(a_i)~ và ~(b_i)~ gọi là tương tự nhau nếu với mọi ~i \neq j~ mà ~a_i = a_j~ thì ~b_i = b_j~ và ~a_i \neq a_j~ thì ~b_i \neq b_j~.

Yêu cầu: Hãy kiểm tra hai dãy số ~(a_i)~ và ~(b_i)~ có tương tự nhau hay không?

INPUT

• Dòng ~1~ ghi một số nguyên dương ~n~.
• Dòng ~2~ ghi ~n~ số nguyên của dãy số ~(a_i)~, mỗi số ghi cách nhau ít nhất một dấu cách.
• Dòng ~3~ ghi ~n~ số nguyên của dãy số ~(b_i)~, mỗi số ghi cách nhau ít nhất một dấu cách.

OUTPUT

Gồm một dòng chứa số ~1~ nếu dãy số ~(a_i)~ và dãy số ~(b_i)~ tương tự nhau và số ~0~ trong trường hợp ngược lại. Nếu ~n~ không thỏa mãn điều kiện bài toán thì ghi là ~-1~.

SUBTASKS

• ~10 \%~ số test ứng với các giá trị của ~n~ không thỏa mãn điều kiện bài toán.
• ~70 \%~ số test ứng với ~1< n ≤ 10^{4}~.
• ~20 \%~ số test ứng với ~1 < n ≤ 5 \times 10^{4}~.

SAMPLE INPUT 1

5
1 2 3 1 3
3 2 1 3 1

SAMPLE OUTPUT 1

1

SAMPLE INPUT 2

5
1 2 3 1 3
1 2 3 3 3

SAMPLE OUTPUT 2

0

Trong một buổi thi lập trình, thầy giáo yêu cầu học sinh gửi tệp bài thi được đặt mật khẩu cùng với một xâu ký tự đã dấu mật khẩu để mở tệp bài thi vào email của thầy giáo. Mật khẩu được dấu trong một xâu ký tự là một xâu con gồm các ký tự khác nhau, không chứa dấu cách trắng và có độ dài lớn nhất. Nếu có nhiều xâu con gồm các ký tự khác nhau, không chứa dấu cách trắng và có độ dài lớn nhất bằng nhau thì xâu con cuối cùng trong xâu ký tự là xâu mật khẩu để mở tệp.

Yêu cầu: Xác định mật khẩu được giấu trong một xâu ký tự.

INPUT

• Dòng ~1~ chứa một số nguyên dương ~n~ ~(1 ≤ n ≤ 2 \times 10^{4})~ là số lượng các dòng văn bản có trong tệp.
• ~n~ dòng tiếp theo, mỗi dòng chứa một xâu không vượt quá ~256~ ký tự bao gồm các chữ cái, chữ số, ký tự đặc biệt, dấu cách trống.

OUTPUT

Gồm các dòng tương ứng là mật khẩu được giấu trong xâu ký tự.

SUBTASKS

• ~50 \%~ số test ứng với ~1 ≤ n ≤ 10^{4}~.
• ~30 \%~ số test ứng với ~10^{4} < n ≤ 1.5 \times 10^{4}~.
• ~20 \%~ số test ứng với ~1.5 \times 10^{4} < n ≤ 2 \times 10^{4}~.

SAMPLE INPUT

3
Good morning!
How are you?
Have a nice day!

SAMPLE OUTPUT

morni
you?
day!

Cho một bảng ~A~ kích thước ~n \times m~ ô, trên mỗi ô ghi một số nguyên dương là số lượng quà mà một con robot cần mang đi. Con robot xuất phát tại một ô ~A[i,1]~ nào đó của cột ~i (1 ≤ i ≤ n)~ cần di chuyển sang một ô lân cận của cột ~j (1 ≤ j ≤ m)~. Cụ thể, từ ô ~A[i, j]~, con robot chỉ được di chuyển sang một trong ba ô sau: ~A[i, j+1], A[i-1, j+1], A[i+1, j+1]~ và khi con robot đi qua ô nào thì mang theo toàn bộ lượng quà ở ô đó.

Yêu cầu: Hãy tìm đường đi cho con robot từ một ô nào đó của cột ~1~ đến một ô nào đó của cột ~m~ để cho tổng lượng quà mà con robot cần mang đi là lớn nhất.

INPUT

• Dòng ~1~ ghi ~2~ số nguyên ~n~ và m cách nhau ít nhất một dấu cách ~(1 ≤ n, m ≤ 1000)~.
• Dòng thứ ~i~ trong ~n~ dòng tiếp theo ghi ~m~ số nguyên dương, mỗi số không vượt quá ~10^{5}~ và hai số liên tiếp cách nhau ít nhất một dấu cách.

OUTPUT

Gồm một dòng là tổng các số chứa trong các ô mà con robot đã đi qua.

SUBTASKS

• ~50 \%~ số test ứng với ~1 ≤ n, m ≤ 500~.
• ~30 \%~ số test ứng với ~500 < n, m ≤ 800~.
• ~20 \%~ số test ứng với ~800 < n, m ≤ 1000~.

SAMPLE INPUT

3 5
7 3 8 1 5
8 8 3 14 1
6 15 19 1 1

SAMPLE OUTPUT

61