Độ khó: Dễ (1/4 điểm)

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 \le R \le 10^6~, hãy tính số lượng các số song nguyên tố thuộc đoạn ~[L, R]~.

Input

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

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~.

Ràng buộc

• 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 (tức là không thỏa ~1 < L \le R \le 10^6~).
• 70% số test ứng với ~1 < L \le R \le 10^4~.
• 20% số test ứng với ~1 < L \le R \le 10^6~.

Lưu ý: Tuy đề bài yêu cầu dữ liệu với file nhưng trên web thì cứ mặc định là đọc từ bàn phím và in ra màn hình nha các bạn

Sample Input

10 30

Sample Output

3

Giải thích

Các số nguyên tố trong đoạn ~[10, 30]~ gồm 11, 13, 17, 19, 23, 29, trong đó có 3 số song nguyên tố là 11, 23 và 29.

Độ khó: Trung bình (2/4 điểm)

Cho hai dãy số nguyên ~a_1, a_2, \ldots, a_n~ và ~b_1, b_2, \ldots, b_n~ với điều kiện ~1 < n \le 5 \cdot 10^4~ và ~1 \le a_i, b_i \le 10^9~ (~i = 1, 2, \ldots, n~). Hai dãy số ~(a_i)~ và ~(b_i)~ gọi là tương tự nhau nếu với mọi ~i \ne j~ mà ~a_i = a_j~ thì ~b_i = b_j~ và ~a_i \ne a_j~ thì ~b_i \ne 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

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~.

Ràng buộc

• 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 (tức là không thỏa ~1 < n \le 5 \cdot 10^4~).
• 70% số test ứng với ~1 < n \le 10^4~.
• 20% số test ứng với ~1 < n \le 5 \cdot 10^4~.

Lưu ý: Tuy đề bài yêu cầu dữ liệu với file nhưng trên web thì cứ mặc định là đọc từ bàn phím và in ra màn hình nha các bạn

Sample Input 1

5
1 2 3 1 3
3 2 1 3 1

Sample Output 1

1

Giải thích 1

Với mọi ~i \ne j~ (~i, j = 1, 2, \ldots, 5~) ta có ~a_i = a_j~ thì ~b_i = b_j~ và ~a_i \ne a_j~ thì ~b_i \ne b_j~, do vậy hai dãy ~(a_i)~ và ~(b_i)~ tương tự nhau.

Sample Input 2

5
1 2 3 1 3
1 2 3 3 3

Sample Output 2

0

Giải thích 2

Ta có ~a_1 = a_4~ nhưng ~b_1 \ne b_4~, do vậy hai dãy ~(a_i)~ và ~(b_i)~ không tương tự nhau.

Độ khó: Dễ (1/4 điểm)

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 dấu trong một xâu ký tự.

Input

Dòng 1 chứa một số nguyên dương ~n~ (~1 \le n \le 2 \cdot 10^4~) là số lượng các dòng văn bản có trong tệp và ~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 ~n~ dòng tương ứng là mật khẩu được dấu trong xâu ký tự.

Ràng buộc

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

Lưu ý: Tuy đề bài yêu cầu dữ liệu với file nhưng trên web thì cứ mặc định là đọc từ bàn phím và in ra màn hình nha các bạn

Sample Input

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

Sample Output

morni
you?
day!

Giải thích

• Xâu ký tự "Good morning!" có các ký tự khác nhau dài nhất là "morni", do vậy "morni" là mật khẩu dấu trong xâu 1.
• Xâu ký tự "How are you?" có các ký tự khác nhau dài nhất là "you?" do vậy "you?" là mật khẩu dấu trong xâu 2.
• Xâu ký tự "Have a nice day!" có các ký tự khác nhau dài nhất là "Have", "nice" và "day!", vì xâu "day!" là xâu con cuối cùng trong 3 xâu nên xâu "day!" là mật khẩu dấu trong xâu 3.

Độ khó: Trung bình (2/4 điểm)

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 1 (~1 \le i \le n~) cần di chuyển sang một ô lân cận của cột ~j~ (~1 \le j \le m~). Cụ thể, từ ô ~A[i, j]~ (~1 \le i \le n~, ~1 \le j \le m~), 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 một ghi 2 số nguyên ~n~ và ~m~ cách nhau ít nhất một dấu cách (~1 \le n, m \le 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

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

Ràng buộc

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

Lưu ý: Tuy đề bài yêu cầu dữ liệu với file nhưng trên web thì cứ mặc định là đọc từ bàn phím và in ra màn hình nha các bạn

Sample Input

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

Sample Output

61

Giải thích

Tổng lớn nhất các số chứa trong các ô mà con robot đã đi qua là 61 (gồm các ô ~A[2, 1], A[3, 2], A[3, 3], A[2, 4], A[1, 5]~).