Hôm nay Ban được học về số palindrome, đó là số mà nếu viết biểu diễn thập phân của nó (không có chữ số 0 ở đầu) ở dạng ngược lại thì ta vẫn được cùng một số. Ví dụ 1221 là một số palindrome trong khi 123 thì không phải. Ban tò mò không biết trong đoạn từ ~L~ tới ~R~ có tất cả bao nhiêu số palindrome mà tổng các chữ số ở dạng thập phân của nó là số nguyên tố. Bạn hãy giúp Ban nhé.

Input Gồm một dòng duy nhất chứa hai số nguyên ~L~ và ~R~ với ~1≤ L≤ R≤10^{12}.~

Output

Một số nguyên duy nhất là số lượng số palindrome mà tổng chữ số ở dạng thập phân của nó là số nguyên tố trong đoạn ~[L,R].~

Sample input

10000 12000

Sample output

9

Giải thích

Có ~9~ số đó là ~10001,10101,10301,10501,10901,11111,11311,11711,11911.~

Subtasks

• Subtask 1 (60% số điểm): ~L,R≤10^6.~
• Subtask 2 (40% số điểm): ~L,R≤10^{12}.~

Anh Phú sau khi giải nghệ ở kỳ thi chuyên Tin thì đã về nuôi gà và trồng thêm hoa. Phú rất thích trồng hoa ly ly và anh xếp ~N~ khóm hoa của mình, được đánh số từ 1 đến ~N~, thành một hàng ngang để đo chiều cao của chúng, khóm hoa thứ ~i~ có chiều cao là ~h_i~. Sau đó anh ta muốn chụp ảnh một số dãy con gồm những khóm hoa liên tiếp nhau để mang đến dự thi cuộc thi nhiếp ảnh tại một hội chợ hoa do thầy Luna tổ chức. Cuộc thi này có một quy định là chỉ những bức ảnh có trung vị chiều cao của những khóm hoa trong ảnh lớn hơn hoặc bằng ~K~ thì mới hợp lệ và được dự thi.

Chú ý: trung vị của một dãy số ~a_1,a_2,...,a_n~ có ~n~ sẽ được tính như sau: sắp xếp dãy tăng dần thì trung vị là ~a_{n/2+1}~ nếu ~n~ chẵn và là ~a_{(n+1)/2}~ nếu ~n~ lẻ.

Hỏi anh Phú có thể chụp được bao nhiêu bức ảnh hợp lệ?

Input

Dòng đầu tiên gồm số nguyên dương ~n, k~ với ~1 \le n \le 10^5~ và ~1 \le k \le 10^9.~

Dòng tiếp theo gồm các số nguyên dương cho biết chiều cao của khóm hoa, không vượt quá ~10^9.~

Output

Số khóm hoa thỏa mãn.

Sample input

4 6
10 5 6 2

Sample output

7

Giải thích: các dãy con sau đây thỏa mãn: ~(10), (6), (5, 6), (10, 5), (5, 6), (6, 2), (10, 5, 6), (10, 5, 6, 2).~

Subtasks

• Subtask 1 (30% số test): ~n \le 500~.
• Subtask 2 (70% số test): Không có ràng buộc gì thêm.

Thành phố Huế có ~n~ địa điểm du lịch và được đánh số từ ~1~ đến ~n~. Các địa điểm được nối với nhau bởi hệ thống giao thông gồm ~m~ tuyến đường hai chiều, mỗi tuyến đường nối trực tiếp một cặp địa điểm, đảm bảo luôn có đường đi lại giữa hai địa điểm bất kì (trực tiếp hoặc đi qua một số địa điểm khác). Team ICPC năm nay của IUH đã lên kế hoạch tham quan các địa điểm du lịch, kết hợp với ăn uống các đặc sản của Huế. Team không mang theo tiền mặt mà dự định sẽ đi rút tiền tại các máy ATM, mỗi khi muốn đi ăn ở đâu đó. Có ~b~ địa điểm trong đó có đặt máy ATM để rút tiền và ~r~ địa điểm ăn uống. Yêu cầu đặt ra là từ một địa điểm ăn uống bất kỳ, hãy giúp team tính ra độ dài của tuyến đường ngắn nhất đến một máy ATM tùy nào nào đó trong ~b~ địa điểm.

Input

Dòng đầu tiên gồm 4 số ~n, m, b, r~ trong đó ~n~ là số địa điểm, ~m~ là số tuyến đường, ~b~ là số vị trí đặt máy ATM và ~r~ là số địa điểm ăn uống (~2 \le n \le 5 \times 10^5; 1 \le m \le 5 \times 10^5; 1 \le b, r \le n.~).

Dòng hai là STT của các vị trí rút tiền, các số phân biệt trong khoảng từ ~1~ đến ~n~.

Dòng ba là STT cả các vị trí ăn uống, các số phân biệt trong khoảng từ ~1~ đến ~n~.

Tiếp theo m dòng là đường đi 2 chiều giữa các địa điểm.

Output

In ra ~r~ số nguyên cho biết độ dài ngắn nhất từ một địa điểm ăn uống thứ ~i~ với ~1 \le i \le n~ đến một máy rút tiền nào đó.

Sample input

6 6 2 3
3 2
1 5 4
1 2
1 6
3 6
2 3
4 5
3 4

Sample output

1 2 1

Giải thích: ~1 \to 2~, ~5 \to 4 \to 3~, ~4 \to 3~.

Subtasks

• Subtask 1: (40% số test): ~2 \le n \le 2000; 1 \le m \le 2000.~
• Subtask 2: (60% số test): Không có ràng buộc gì thêm.

Sau nhiều năm theo đuổi IOI không thành, bạn quyết định từ bỏ và thành lập một công ty cung cấp các dịch vụ tính toán trên đám mây. Để làm được điều này, trước tiên bạn phải mua một số máy tính mạnh để đáp ứng được nhu cầu của khách hàng. Bạn vào một cửa hàng bán máy tính để tìm mua những chiếc máy tính có cấu hình mạnh. Cửa hàng có n máy tính, máy tính thứ ~i~ với ~1 ≤ i ≤ N~ có số lượng lõi (core) là ~c_i~, tốc độ tính toán ~f_i~ và giá là ~v_i~. Biết ~c_i~ lõi của máy tính là độc lập với nhau nên máy tính có thể thực hiện ~c_i~ công việc đồng thời.

Tuy chưa mua được máy tính nhưng bạn đã có được ~m~ đơn đặt hàng. Đơn đặt hàng thứ ~i~ với ~1 ≤ i ≤ m~ yêu cầu thuê đúng ~C_i~ lõi, mỗi lõi phải có tốc độ tính toán ít nhất là ~F_i~. Nếu bạn chấp nhận đơn đặt hàng này, bạn cần phải chọn ~C_i~ lõi (có thể từ những máy tính khác nhau) có tốc độ tính toán ít nhất là ~F_i~, cho khách hàng thuê và bạn sẽ được trả ~V_i~ tiền. Tất nhiên, một lõi chỉ có thể được thuê bởi nhiều nhất một khách hàng.

Yêu cầu: hãy tìm cách mua máy tính và cách chấp nhận đơn đặt hàng sao cho lợi nhuận là lớn nhất có thể, trong đó lợi nhuận được tính bằng tổng tiền bạn nhận được từ khách hàng trừ đi chi phí mua máy tính.

Input

Dòng đầu tiên chứa số nguyên ~n~ với ~1 ≤ n ≤ 2000~ là số lượng máy tính có thể mua.

Trong ~n~ dòng sau, dòng thứ ~i~ chứa 3 số nguyên ~c_i, f_i, v_i~ với ~1 ≤ c_i ≤ 50, 1 ≤ f_i ≤ 10^9, 1 ≤ v_i ≤ 10^9~.

Dòng tiếp theo chứa số nguyên ~m~ với ~1 ≤ m ≤ 200~ là số lượng đơn đặt hàng.

Trong ~m~ dòng sau, dòng thứ ~i~ chứa 3 số nguyên ~C_i, F_i, V_i~ với ~1 ≤ Ci ≤ 50, 1 ≤ F_i ≤ 10^9, 1 ≤ Vi ≤ 10^9~.

Output

Một dòng chứa lợi nhuận lớn nhất có thể.

Sample input

4
4 2200 700
2 1800 10
20 2550 9999
4 2000 750
3
1 1500 300
6 1900 1500
3 2400 4550

Sample output

350

Giải thích chiến lược như sauu: mua 2 máy tính, trong đó máy tính thứ 1 và thứ 4, bạn có ~8~ lõi và chi phí mua là: ~700+750=1450~. Chấp nhận 2 đơn đặt hàng đầu tiên, cần cung cấp 7 lõi cho khách hàng, số tiền thu được là: ~300+1500=1800~ nên lợi nhuận là: ~1800-1450 = 350.~ Dễ dàng chứng minh được đây là lợi nhuận tối ưu.

Subtask:

• Subtask 1: ~n ≤ 15~
• Subtask 2: ~m ≤ 15~
• Subtask 3: ~n, m ≤ 250~ và ~c_i = C_j = 1~ với mọi ~i, j~.
• Subtask 4: ~f_i = F_j = 1~ với mọi ~i, j.~
• Subtask 5: ~v_i = V_j = 1~ với mọi ~i, j.~ Subtask 6: Không có ràng buộc gì thêm