Số nguyên tố là lớp số tự nhiên đặc biệt đã được con người nghiên cứu từ hơn 2500 năm qua. Đây là tập hợp vô tận các số tự nhiên mà không có ước số nào khác ngoài 1 và chính nó.

Tập số nguyên tố thường được ký hiệu là ~P = { 2, 3, 5, 7, 11, 13, 17, 19,… }~

Nhiệm vụ của bạn là tính tổng các số nguyên tố không vượt quá ~N~.

Input:

• Số nguyên dương ~N~, giá trị không quá 1 tỉ.

Output:

• Tổng các số nguyên tố không vượt quá ~N~.

Sample Input 1

100

Sample Output 1

1060

Sample Input 2

1000

Sample Output 2

76127

Hàm G(x) được định nghĩa như sau:

~G(x) = x^2 + 2x + 3~

Tất nhiên biết giá trị x ta sẽ dễ dàng tính được G(x), và việc tính hàm G lồng nhau như dưới đây cũng không quá khó:

~F(n, x) = \underbrace{G(G(G(...G(G(x))...)))}_{\text{Lồng nhau n lần}} \% 10^9~

Input:

• Hai số nguyên dương ~N~ và ~X~, giá trị không quá 1 tỉ.

Output:

• Giá trị của ~F(n, x)~

Sample Input 1

2 1

Sample Output 1

51

Sample Input 2

3 3

Sample Output 2

132498

Sample Input 3

10 123

Sample Output 3

550273643

Lưới ô kích thước ~M \times N~, mỗi ô vuông điền một số tự nhiên không quá 6 chữ số. Chỉ hai ô chung cạnh mới có thể đi được trực tiếp sang nhau.

Ta gọi chi phí đường đi từ ô ~(x, y)~ tới ô ~(p, q)~ là tổng các số trên các ô thuộc đường đi. Ví dụ như một đường đi từ ô ~(0, 0)~ tới ô ~(2, 3)~ gồm các ô được tô màu vàng và chi phí là 13. Tất nhiên có nhiều đường đi nhưng ta chỉ quan tâm đến chi phí nhỏ nhất, trong trường hợp này đúng là bằng 13.

Xuất phát từ một ô ~(p, q)~ bất kỳ, ta có thể tính toán chi phí nhỏ nhất đi đến mọi ô khác trên lưới bằng nhiều cách, nhưng cuối cùng ta sẽ được một ma trận mà ô ~(x, y)~ điền chi phí thấp nhất từ ~(p, q)~ đến ~(x, y)~, ta gọi đây là ma trận chi phí.

Yêu cầu: cho lưới ~M \times N~, hãy tính số ~K~ là tổng tất cả các phần tử của ma trận chi phí tương ứng (~M~ và ~N~ không quá ~1000~).

Input:

• Dòng đầu ghi 4 số ~m, n, p~ và ~q~.
• ~M~ dòng tiếp sau: mỗi dòng ghi đúng ~N~ số là ~N~ giá trị điền trên dòng tương ứng.

Output:

• Số ~K~

Dữ liệu ứng với hình vẽ trên và xuất phát từ ô ~(0, 0)~

Sample Input 1

3 4 0 0
4 2 5 3
3 3 1 2
0 9 9 1

Sample Output 1

128

Giải thích: OUTPUT ~128~ ứng với tổng các số trên ma trận chi phí dưới đây: