Cho dãy ~A~ gồm ~n~ phần tử ~a_1, a_2, ..., a_n~.

Yêu cầu

Hãy lập trình tính tổng các phần tử có chữ số hàng đơn vị lớn hơn chữ số hàng chục trong dãy.

Dữ liệu đầu vào

Gồm hai dòng:

• Dòng đầu tiên chứa số nguyên dương ~n~ ~(1 \le n \le 10^6)~.
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ ~(10 \le a_i \le 10^6;\ 1 \le i \le n)~.

Dữ liệu đầu ra

Gồm một số nguyên duy nhất là tổng tìm được.

Ràng buộc dữ liệu

• Có 40% số test tương ứng với 40% số điểm của bài có ~n \le 10^3;\ a_{i} \le 10^3~.
• Có 30% số test tương ứng với 30% số điểm của bài có ~n \le 10^3;\ a_{i} \le 10^6~.
• Có 30% số test tương ứng với 30% số điểm của bài ~10^3 < n \le 10^6~.

Ví dụ

Ví dụ 1

INPUT

5
15 141 28 66 79

OUTPUT

122

Gia đình Thỏ Con vừa xây xong một căn nhà khang trang, công việc tiếp theo là hoàn thiện nội thất bên trong. Thỏ Con được bố mẹ giao nhiệm vụ tìm mua hai bức tranh để trang trí phòng khách.

Tại cửa hàng có tất cả ~n~ bức tranh đánh số từ ~1~ đến ~n~ đang được bày bán. Bức tranh thứ ~i~ có mã màu là ~a_i~.

Thỏ Con muốn mua hai bức tranh sao cho màu sắc của chúng tương đồng nhau, tức là hiệu số mã màu của hai bức tranh đó phải không lớn hơn ~X~.

Yêu cầu

Hãy cho biết Thỏ Con có bao nhiêu cách chọn ra hai bức tranh để mua đảm bảo màu sắc tương đồng nhau.

Dữ liệu đầu vào

Gồm hai dòng:

• Dòng đầu tiên chứa hai số nguyên dương ~n, X~ ~(n \le 10^7;\ X \le 10^6)~;
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ ~(a_i \le 10^6;\ 1 \le i \le n)~.

Dữ liệu đầu ra

Gồm một số nguyên duy nhất là số cách chọn ra hai bức tranh để mua thỏa mãn yêu cầu đề bài.

Ràng buộc dữ liệu

• Có 40% số test tương ứng với 40% số điểm của bài có ~n \le 10^3~.
• Có 30% số test tương ứng với 30% số điểm của bài có ~10^3 < n \le 10^5~.
• Có 30% số test tương ứng với 30% số điểm của bài có ~10^5 < n \le 10^7~.

Ví dụ

Ví dụ 1

INPUT

4 3
5 6 9 2

OUTPUT

3

Giải thích: Có các cách chọn sau:

• Chọn tranh ~1~ và ~2~;
• Chọn tranh ~1~ và ~4~;
• Chọn tranh ~2~ và ~3~.

Nhân dịp đầu năm mới, Đoàn Thanh niên tổ chức chương trình khai xuân cho học sinh chơi các trò chơi. Có tất cả ~n~ học sinh ~(1 \le n \le 10^9)~ đăng ký tham gia, các bạn học sinh này được xếp thành hàng ngang và đánh số từ ~1~ đến ~n~.

Có tất cả ~k~ ~(1 \le k \le 10^6)~ trò chơi, trò chơi thứ ~i~ gồm các bạn học sinh có số thứ tự từ ~l_i~ đến ~r_i~ được tham gia, sau khi tham gia xong trò chơi đó học sinh quay về vị trí cũ trong hàng.

Yêu cầu

Kết thúc chương trình, Ban Tổ chức muốn biết ~q~ ~(1 \le q \le 10^6)~ bạn học sinh có số thứ tự lần lượt là ~b_1, b_2, ..., b_q~ mỗi bạn đã được tham gia bao nhiêu trò chơi?

Dữ liệu đầu vào

Gồm ~k + 2~ dòng:

• Dòng đầu tiên chứa ba số nguyên dương ~n, k, q~.
• Dòng thứ ~i~ trong ~k~ dòng tiếp theo chứa hai số nguyên dương ~l_i, r_i~ ~(1 \le l_i \le r_i \le n)~.
• Dòng cuối cùng chứa ~q~ số nguyên dương ~b_1, b_2, ..., b_q~ ~(1 \le b_i \le n;\ 1 \le i \le q)~.

Dữ liệu đầu ra

Gồm ~q~ dòng, dòng thứ ~i~ ~(1 \le i \le q)~ chứa một số nguyên là số lượng trò chơi mà học sinh bị đã tham gia.

Ràng buộc dữ liệu

• Có 40% số test tương ứng với 40% số điểm của bài có ~1 \le n, k, q \le 10^3~.
• Có 30% số test tương ứng với 30% số điểm của bài có ~n \le 10^6~.
• Có 30% số test tương ứng với 30% số điểm của bài có ~10^6 < n \le 10^9~.

Ví dụ

Ví dụ 1

INPUT

10 2 3
3 9
8 9
6 8 2

OUTPUT

1
2
0

Cho một đồ thị vô hướng, liên thông gồm ~n~ đỉnh được đánh số từ ~1~ đến ~n~ và ~m~ cạnh được đánh số từ ~1~ đến ~m~. Cạnh thứ ~i~ nối đỉnh ~u_{i}~ với đỉnh ~v_{i}~ và có trọng số ~w_{i}~ mỗi cạnh của đồ thị ta có thể tăng thêm một đại lượng nguyên không âm để trọng số của cạnh đó là một số nguyên tố.

Yêu cầu

Hãy tìm một đường đi từ đỉnh ~s~ đến đỉnh ~t~ chỉ đi qua các cạnh có trọng số là số nguyên tố (sau khi đã tăng) với tổng giá trị tăng của các cạnh là nhỏ nhất có thể.

Dữ liệu đầu vào

Gồm ~m + 1~ dòng:

• Dòng thứ nhất gồm bốn số nguyên dương ~n, m, s, t~ ~(n, m \le 10^5;\ s, t \le n)~.
• Dòng thứ ~i~ trong ~m~ dòng sau chứa ba số nguyên dương ~u_i, v_i, w_i~ ~(1 \le u_i, v_i \le n;\ w_i \le 10^6)~.

Dữ liệu đầu ra

Gồm một số nguyên duy nhất là tổng giá trị tăng nhỏ nhất của các cạnh tìm được.

Ràng buộc dữ liệu

• Có 20% số test tương ứng với 20% số điểm của bài có ~u_i + 1 = v_i\ \forall i = 1..m~.
• Có 40% số test tương ứng với 40% số điểm của bài có ~n, m \le 2000~.
• Có 40% số test tương ứng với 40% số điểm của bài có ~2000 < n, m \le 10^5~.

Ví dụ

Ví dụ 1

INPUT

4 5 1 4
1 2 20
1 3 3
2 4 10
3 4 6
1 4 15

OUTPUT

1

Giải thích: