Cho một dãy gồm ~N~ số nguyên dương ~a_1, a_2, \dots, a_n~ và một số nguyên dương ~K~.

Hãy tìm tổng của tất cả các phần tử trong dãy chia hết cho ~K~. Nếu không có phần tử nào chia hết cho ~K~, in ra ~0~.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~N~ và ~K~ (~1 \le N \le 10^5, 1 \le K \le 10^9~).

• Dòng thứ hai chứa ~N~ số nguyên dương ~a_1, a_2, \dots, a_n~ (~1 \le a_i \le 10^9~).

Output

In ra một số nguyên duy nhất: tổng của các phần tử chia hết cho ~K~.

Scoring

Sample Input 1

5 3
6 7 9 2 12

Sample Output 1

27

Notes

Chia hết cho 3: 6, 9, 12.

Tổng = 6 + 9 + 12 = 27.

Một cửa hàng có ~4~ loại nguyên liệu và ~4~ công thức. Mỗi nguyên liệu có một chỉ số chất lượng ~a_i~ và mỗi công thức có một hệ số khó ~b_j~. Khi kết hợp nguyên liệu ~i~ với công thức ~j~, điểm thành phẩm là: ~điểm = a_i \times b_j~

Bạn được chọn đúng một nguyên liệu và đúng một công thức. Hãy tìm điểm thành phẩm lớn nhất có thể.

Input

• Dòng thứ nhất chứa ~4~ số nguyên: ~a_1, a_2, a_3, a_4~ (~-10^9 \le a_i \le 10^9~).

• Dòng thứ hai chứa ~4~ số nguyên: ~b_1, b_2, b_3, b_4~ (~-10^9 \le b_j \le 10^9~).

Output

In ra một số duy nhất: điểm thành phẩm lớn nhất có thể.

Scoring

Sample Input 1

3 -2 5 1
3 -5 7 1

Sample Output 1

35

Notes

Ghép ~a_3 = 5~ với ~b_3 = 7~: ~5 \times 7 = 35~.

Bạn có ba chiếc cốc có dung tích lần lượt là ~A, B~ và ~C~ lít. Ban đầu, cốc 1 chứa đầy nước (~A~ lít), cốc 2 và cốc 3 đều rỗng.

Bạn được cho một danh sách gồm ~N~ thao tác. Mỗi thao tác có dạng ~u~ ~v~ (~1 \le u, v \le 3, u \neq v~), nghĩa là rót nước từ cốc ~u~ sang cốc ~v~. Khi rót, bạn rót cho đến khi cốc ~u~ hết nước hoặc cốc ~v~ đầy, tùy điều kiện nào xảy ra trước.

Hãy in ra lượng nước trong ba cốc sau khi thực hiện xong.

Input

• Dòng đầu tiên chứa ba số nguyên dương ~A, B, C~ (~1 \le A, B, C \le 10^9~) — dung tích của ba cốc.

• Dòng thứ hai chứa một số nguyên dương ~N~ (~1 \le N \le 10^5~) — số lượng thao tác.

• ~N~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u~ và ~v~ (~1 \le u, v \le 3, u \neq v~).

Output

In ra ba số nguyên trên một dòng, cách nhau bởi dấu cách: lượng nước trong cốc 1, cốc 2 và cốc 3.

Scoring

Sample Input 1

10 7 3
5
1 2
2 3
3 1
2 3
1 2

Sample Output 1

0 7 3

Sample Input 2

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

Sample Output 2

3 3 0

Notes

Test 1:

• Ban đầu: (10, 0, 0)

• 1 ~\rightarrow~ 2: (3, 7, 0)

• 2 ~\rightarrow~ 3: (3, 4, 3)

• 3 ~\rightarrow~ 1: (6, 4, 0)

• 2 ~\rightarrow~ 3: (6, 1, 3)

• 1 ~\rightarrow~ 2: (0, 7, 3)

Test 2:

• Ban đầu: (6, 0, 0)

• 1 ~\rightarrow~ 2: (2, 4, 0)

• 2 ~\rightarrow~ 3: (2, 1, 3)

• 1 ~\rightarrow~ 2: (0, 3, 3)

• 2 ~\rightarrow~ 3: (0, 3, 3) — không đổi

• 3 ~\rightarrow~ 1: (3, 3, 0)

Một nông trại có ~N~ thửa ruộng xếp thành một hàng, thửa thứ ~i~ có giá trị thu hoạch là ~a_i~ (có thể âm, nghĩa là thửa đó bị sâu bệnh và gây thiệt hại nếu thu hoạch).

Bạn muốn chọn một số thửa để thu hoạch sao cho tổng giá trị lớn nhất có thể. Tuy nhiên, sau khi thu hoạch một thửa, máy gặt cần thời gian bảo trì nên bạn phải bỏ qua ít nhất ~K~ thửa liền kề tiếp theo trước khi thu hoạch thửa tiếp.

Nói cách khác, nếu bạn thu hoạch thửa ~i~, thửa tiếp theo bạn được phép thu hoạch sớm nhất là thửa ~i + K + 1~. Bạn cũng có thể chọn không thu hoạch thửa nào (tổng = ~0~).

Hãy tìm tổng giá trị thu hoạch lớn nhất có thể.

Input

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~K~ (~1 \le N \le 10^6, 0 \le K \le N-1~).

• Dòng thứ hai chứa ~N~ số nguyên ~a_1, a_2, \dots, a_n~ (~-10^9 \le a_i \le 10^9~).

Output

In ra một số nguyên duy nhất: tổng giá trị thu hoạch lớn nhất.

Scoring

Sample Input 1

5 1
3 1 5 2 8

Sample Output 1

16

Sample Input 2

6 2
5 -3 4 -1 6 2

Sample Output 2

11

Sample Input 3

4 1
-5 -3 -1 -4

Sample Output 3

0

Notes

Test 1: Thu hoạch thửa 1, 3, 5: ~3 + 5 + 8 = 16~.

Test 2: Thu hoạch thửa 1 và 5: ~5 + 6 = 11~.

Test 3: Tất cả âm, không thu hoạch.

Kiên đang đi du lịch trên hòn đảo cá nhân của Khôi Anh. Ở giữa hòn đảo có một ngôi đền trông rất đẹp, Kiên rất mong muốn được vào tham quan nhưng ngay trước cổng vào có ~T~ câu đố, ~1 \le T \le 100~. Mỗi câu đố cho hai số nguyên ~0 \le L \le R \le 10^{100000}~, yêu cầu tìm số lượng số tự nhiên ~x~ thỏa mãn ~2^x~ có cùng số dư với ~x^2~ khi chia cho ~7~ và ~L \le x \le R~.

Tuy nhiên, Kiên lại không giỏi trong việc giải những câu đố nên nhờ bạn giúp. Bạn hãy giúp Kiên nhé.

Input

• Dòng đầu tiên gồm 2 số nguyên dương ~subtask\_id~ (~1 \le subtask\_id \le 4~) và số lượng câu đố ~T~ (~1 \le T \le 10~).

• ~T~ dòng tiếp theo mỗi dòng gồm 2 số tự nhiên ~L, R~ (~0 \le L \le R \le 10^{100000}~).

Output

In ra ~T~ dòng, mỗi dòng gồm 1 số nguyên là số lượng giá trị ~x~ thỏa mãn điều kiện của câu đố tương ứng.

Scoring

Sample Input 1

1 2
0 20
36 67

Sample Output 1

6
9

Notes

Các số tự nhiên ~x~ thỏa mãn ở câu đố thứ nhất là ~2, 4, 5, 6, 10, 15~ và ở câu đố thứ hai là ~36, 44, 46, 47, 48, 52, 57, 65, 67~.

Trong lúc dạo quanh trên hòn đảo của Khôi Anh, Kiên phát hiện một căn hầm bỏ hoang đầy bí ẩn với vô vàn những viên đá quý lấp lánh. Tuy nhiên, Kiên chỉ mang theo một chiếc túi nhỏ chứa được tối đa ~S~ kg, trong khi căn phòng lại có tới ~n~ viên đá quý với viên thứ ~i~ có khối lượng ~w_i~ kg và có giá trị là ~v_i~ tiền. Vì muốn kiếm tiền nhưng lười biếng, Kiên nhờ bạn hãy giúp anh ấy chọn đá vào túi sao cho mỗi viên đá chỉ được lấy một lần mà đồng thời kiếm được nhiều lợi nhuận nhất.

Input

• Dòng đầu gồm ~3~ số ~subtask\_id~ (~1 \le subtask\_id \le 3~), ~n, S~ là số thứ tự của subtask, số viên đá trong phòng và tải trọng tối đa của túi.

• Trong ~n~ dòng tiếp theo, dòng thứ ~i~ gồm một cặp số (~w_i, v_i~) biểu thị khối lượng và giá trị của từng viên đá.

Output

In ra một số thực là số tiền tối đa có thể kiếm được, làm tròn đến 6 chữ số sau dấu phẩy.

Scoring

Sample Input 1

1 5 67
67 90
40 61
26 41
66 101
6 7

Sample Output 1

102.000000

Notes

Chọn viên đá quý thứ 2 và thứ 3, tổng cân nặng là 66 và tổng giá trị là 102.