Số nguyên dương ~d~ được gọi là ước của số nguyên dương ~N~ nếu ~N~ chia hết cho ~d~. Ví dụ: các ước của ~9~ là ~1, 3~ và ~9;~ các ước của ~10~ là ~1, 2, 5~ và ~10~.

Yêu cầu: Cho hai số nguyên dương ~L~ và ~R~ ~(L ≤ R)~. Hãy tính tổng của tất cả các số nguyên dương là ước của ít nhất một số trong đoạn từ ~L~ tới ~R~ ~(~bao gồm cả ~L~ và ~R)~.

Dữ liệu vào từ tệp văn bản SUMDIV.INP:

Gồm một dòng chứa hai số nguyên dương ~L~ và ~R~ ~(1 ≤ L ≤ R ≤ 10^9).~

Kết quả ghi ra tệp văn bản SUMDIV.OUT:

Một số nguyên duy nhất là tổng của tất cả các số nguyên dương là ước của ít nhất một số trong đoạn từ ~L~ tới ~R~.

Ràng buộc

• Có ~20\%~ số test ứng với ~R ≤ 1000~;
• ~25\%~ số test khác ứng với ~R - L ≤ 1000~;
• ~25\%~ số test khác ứng với ~R ≤ 10^6~;
• ~30\%~ số test còn lại không có điều kiện gì thêm.

Ví dụ

Input

9 12

Output

63

Giải thích

Các số là ước của ít nhất một số trong đoạn ~[9, 12]~ là: ~1, 2, 3, 4, 5, 6, 9, 10, 11~ và ~12~ ~(7~ và ~8~ không nằm trong danh sách này vì cả ~9, 10, 11~ và ~12~ đều không chia hết cho ~7~ hoặc ~8)~.

Ta có ~1 + 2 + 3 + 4 + 5 + 6 + 9 + 10 + 11 + 12 = 63~.

Input

7 7

Output

8

Giải thích

Các số là ước của ~7~ là ~1~ và ~7~. Ta có ~1 + 7 = 8~.

Mít có các que tính có nhiều độ dài và màu sắc. Hôm nay học về hình tam giác nhọn, Mít đã nghĩ ra một bài toán rất độc đáo có liên quan tới tam giác nhọn và các que tính của mình. Mít chia các que tính thành ~N~ bộ, các que tính trong cùng một bộ thì có độ dài bằng nhau nhưng có màu khác nhau. Độ dài của các que tính trong hai bộ bất kì là khác nhau. Mít đố các bạn đếm xem có bao nhiêu tam giác nhọn khác nhau có thể được tạo ra từ ~N~ bộ que tính đó. Chú ý: mỗi cạnh của tam giác được chọn từ một bộ que tính khác nhau tức là sẽ không có tam giác cân và hai tam giác nhọn được gọi là giống nhau khi các cặp cạnh tương ứng bằng nhau và cùng màu, ngược lại là khác nhau.

Yêu cầu: Cho độ dài và số lượng các que tính của ~N~ bộ que tính, hãy lập trình đếm số lượng tam giác nhọn khác nhau có thể tạo ra.

Dữ liệu vào từ tệp văn bản TRIACU.INP:

• Dòng đầu tiên gồm một số nguyên dương ~N~ ~(N ≤ 2000)~ là số bộ que tính;
• ~N~ dòng sau, dòng thứ ~i~ chứa hai số nguyên dương ~L, C~ mô tả độ dài và số lượng que tính của bộ thứ ~i~ ~(1 ≤ i ≤ N~; ~\ L ≤ 10^6~; ~\ C ≤ 10^3)~.

Kết quả ghi ra tệp văn bản TRIACU.OUT:

Một số nguyên duy nhất là số lượng tam giác nhọn khác nhau.

Ràng buộc

• Có ~50\%~ số test ứng với ~N ≤ 200~;
• ~50\%~ số test còn lại không có điều kiện gì thêm.

Ví dụ

Input

4
3 3
4 1
5 2
6 2

Output

4

Giải thích

Có ~4~ tam giác nhọn có thể tạo ra từ bộ que tính thứ ~2, 3, 4~.

Giá trị nén của một số nguyên dương ~X~ kí hiệu là ~N(X)~, được tính bằng tích các chữ số của nó. Ví dụ: ~N(123) = 6~, ~N(90) = 0~.

Yêu cầu: Cho hai số nguyên dương ~L, R~ ~(L ≤ R)~, tìm giá trị nén lớn nhất của các số nguyên không bé hơn ~L~ và không lớn hơn ~R~.

Dữ liệu vào từ tệp văn bản COMNUM.INP:

Gồm một dòng duy nhất chứa hai số nguyên dương ~L, R~.

Kết quả ghi ra tệp văn bản COMNUM.OUT:

Một số nguyên duy nhất là giá trị nén lớn nhất của các số thỏa mãn điều kiện đề bài.

Ràng buộc

• Có ~20\%~ số test ứng với ~L ≤ R ≤ 10^6~;
• ~30\%~ số test khác ứng với ~L ≤ R ≤ 10^{18}~;
• ~20\%~ số test khác ứng với ~L ≤ R ≤ 10^{100}~;
• ~30\%~ số test còn lại ứng với ~L ≤ R ≤ 10^{100000}~.

Ví dụ

Input

15 24

Output

9

Trong thành phố có ~N~ trạm tiếp sóng. Trên bản thiết kế xây dựng, trạm thứ ~i~ có tọa độ là ~(x_i, y_i)~. Giữa hai trạm ~i~ và ~j~, chi phí để liên kết hai trạm này với nhau là ~\min(|x_i − x_j|, |y_i − y_j|)~. Lãnh đạo thành phố muốn liên kết toàn bộ các trạm tiếp sóng với nhau (hai trạm được gọi là có liên kết với nhau khi chúng có liên kết trực tiếp với nhau hoặc liên kết qua một số trạm trung gian khác).

Yêu cầu: Hãy giúp lãnh đạo thành phố tính tổng chi phí nhỏ nhất để liên kết toàn bộ ~N~ trạm tiếp sóng.

Dữ liệu vào từ tệp văn bản BTS.INP:

• Dòng đầu tiên ghi số nguyên ~N~ ~(2 ≤ N ≤ 10^5)~ là số trạm tiếp sóng;
• ~N~ dòng tiếp theo, dòng thứ ~i~ ghi hai số nguyên ~x_i~ và ~y_i~ ~(1 ≤ i ≤ N~; ~\ 1 ≤ x_i ≤ 10^9~; ~\ 1 ≤ y_i ≤ 10^9)~ là tọa độ của trạm tiếp sóng thứ ~i~.

Kết quả ghi ra tệp văn bản BTS.OUT:

Một số nguyên duy nhất là tổng chi phí nhỏ nhất để liên kết các trạm tiếp sóng trên.

Ràng buộc

• Có ~50\%~ số test ứng với ~N ≤ 10^3~;
• ~50\%~ số test còn lại không có điều kiện gì thêm.

Ví dụ

Input

5
4 9
9 5
0 2
7 1
3 4

Output

5

Giải thích

• Liên kết giữa trạm ~2~ và ~4~ với chi phí ~2~.
• Liên kết giữa trạm ~3~ và ~4~ với chi phí ~1~.
• Liên kết giữa trạm ~2~ và ~5~ với chi phí ~1~.
• Liên kết giữa trạm ~1~ và ~5~ với chi phí ~1~.

Tổng chi phí sẽ là: ~2 + 1 + 1 + 1 = 5~.

Trên hệ trục tọa độ vuông góc ~Oxy~, cho tọa độ ~N~ điểm trong đó không có ba điểm nào thẳng hàng.

Yêu cầu: Tìm hai điểm trong ~N~ điểm để đường thẳng chứa hai điểm đó chia ~N-2~ điểm còn lại thành hai phần sao cho tổng số điểm của mỗi phần chênh lệnh nhau không quá ~1~.

Dữ liệu vào từ tệp văn bản DIVPOINT.INP:

• Dòng đầu tiên gồm một số nguyên dương ~N~ ~(N ≤ 10^5)~ là số lượng điểm;
• ~N~ dòng sau, mỗi dòng chứa hai số nguyên ~x, y~ là toạ độ của một điểm ~(|x| ≤ 10^9~; ~\ |y| ≤ 10^9)~.

Kết quả ghi ra tệp văn bản DIVPOINT.OUT:

Một dòng gồm bốn số nguyên là toạ độ của hai điểm thoả mãn. Có thể có nhiều kết quả, ghi ra một kết quả bất kì.

Ràng buộc

• Có ~30\%~ số test ứng với ~N ≤ 100~;
• ~30\%~ số test khác ứng với ~N ≤ 5000~;
• ~40\%~ số test còn lại ứng với ~N ≤ 10^5~.

Ví dụ

Input

4
0 0
0 1
1 1
1 0

Output

0 0 1 1

Trên trục ~Ox~, cho ~N~ đoạn thẳng được đánh số từ ~1~ tới ~N~, đoạn thẳng thứ ~i~ ~(1 ≤ i ≤ N)~ nối điểm có tọa độ nguyên ~x = a_i~ và điểm có tọa độ nguyên ~x = b_i~ ~(a_i < b_i)~. Một điểm được gọi là thuộc đoạn thẳng thứ ~i~ nếu tọa độ của nó nằm trong đoạn ~[a_i, b_i]~.

Yêu cầu: Cho biết ~N~ đoạn thẳng và một số nguyên dương ~K~. Hãy viết một chương trình trả lời ~Q~ truy vấn. Ở truy vấn thứ ~j~ ~(1 ≤ j ≤ Q)~, khi cho biết hai số nguyên ~c_j~ và ~d_j~, bạn cần xác định giá trị ~L~ lớn nhất sao cho tồn tại hai số nguyên ~u, v~ thỏa mãn:

• ~c_j ≤ u < v ≤ d_j~ và ~v − u = L~;
• Tồn tại không quá ~K~ đoạn thẳng trong số ~N~ đoạn thẳng được cho sao cho mọi điểm ~x~ có tọa độ nguyên trong đoạn ~[u, v]~ đều thuộc ít nhất một trong các đoạn thẳng đó.

Nếu không tồn tại ~u, v~ nào thì ~L = 0~.

Dữ liệu vào từ tệp văn bản SEGMENT.INP:

• Dòng đầu tiên chứa ba số nguyên dương ~N,Q,K~ ~(1 ≤ K ≤ N ≤ 10^5, \ 1 ≤ Q ≤ 10^5)~;
• ~N~ dòng tiếp theo, dòng thứ ~i~ ~(1 ≤ i ≤ N)~ chứa hai số nguyên ~a_i~ và ~b_i~ ~(0 ≤ a_i < b_i ≤ 10^9)~;
• ~Q~ dòng cuối cùng, dòng thứ ~j~ ~(1 ≤ j ≤ Q)~ chứa hai số nguyên ~c_j~ và ~d_j~ ~(0 ≤ c_j < d_j ≤ 10^9)~.

Kết quả ghi ra tệp văn bản SEGMENT.OUT:

Gồm ~Q~ dòng, dòng thứ ~j~ ~(1 ≤ j ≤ Q)~ là giá trị ~L~ lớn nhất cho truy vấn thứ ~j~.

Ràng buộc

• Có ~20\%~ số test ứng với ~K = 1~; ~\ N,Q ≤ 2000~;
• ~20\%~ số test khác ứng với ~K = 1~;
• ~20\%~ số test khác ứng với ~K = 2~;
• ~20\%~ số test khác ứng với ~K ≤ 30~;
• ~20\%~ số test còn lại không có điều kiện gì thêm.

Ví dụ

Input

3 4 1
6 8
1 5
4 6
1 10
2 6
4 7
5 9

Output

4
3
2
2

Giải thích

• Truy vấn ~1~: chọn ~[u, v] = [1, 5]~.
• Truy vấn ~2~: chọn ~[u, v] = [2, 5]~.
• Truy vấn ~3~: chọn ~[u, v] = [4, 6]~.
• Truy vấn ~4~: chọn ~[u, v] = [6, 8]~.

Input

4 3 2
2 5
6 8
9 11
8 10
1 8
6 11
8 11

Output

3
4
3

Giải thích

• Truy vấn ~1~: chọn ~[u, v] = [2, 5]~.
• Truy vấn ~2~: chọn ~[u, v] = [6, 10]~.
• Truy vấn ~3~: chọn ~[u, v] = [8, 11]~.

Trong giờ sinh hoạt lớp, cô giáo tổ chức cho các bạn học sinh chơi một trò chơi "Tô màu dãy ô vuông". Ban đầu, cô giáo chuẩn bị một dãy các ô vuông xếp cạnh nhau và được đánh số từ ~1~ đến ~N~ và được tô toàn bộ màu có số hiệu là ~0~. Trò chơi diễn ra trong ~M~ lượt chơi, mỗi lượt cô gọi một học sinh bất kì lên tô màu dải ô vuông: học sinh sẽ nghĩ ra ba số nguyên dương ~L, R, C~ ~(L ≤ R)~ và thực hiện tô màu có số hiệu ~C~ từ ô ~L~ đến ô ~R~ (màu của ô vuông sẽ là màu của người tô sau). Kết thúc ~M~ lượt chơi rất hăng say, được một dãy ô vuông rất đẹp, cô giáo bảo các bạn ghi lại ba số ~L, R, C~ mà các bạn nghĩ ra ở lượt chơi của mình và cô giáo đánh số lại các lượt chơi từ ~1~ đến ~M~. Sau đó, cô giáo đố các bạn một câu hỏi rất hóc búa: từ danh sách ghi thông tin tô màu của các bạn học sinh, hãy đưa ra thứ tự các lượt tô màu để từ dãy ô vuông ban đầu thu được dãy ô vuông khi trò chơi kết thúc.

Yêu cầu: Hãy giúp các bạn học sinh sắp xếp lại thứ tự các lượt tô màu.

Dữ liệu vào từ tệp văn bản COLOR.INP:

• Dòng đầu tiên chứa hai số nguyên dương ~N~ và ~M~ ~(1 ≤ N, M ≤ 5 \times 10^5)~ là số ô vuông và số lượt tô màu~;~
• ~M~ dòng sau, mỗi dòng thứ ~i~ chứa ba số nguyên ~L_i, R_i, C_i~ ~(1 ≤ i ≤ M;~ ~\ 1 ≤ L_i ≤ R_i ≤ N;~ ~\ 1 ≤ C_i ≤ 5 \times 10^5)~ mô tả dòng thứ ~i~ ở danh sách ghi thông tin một lượt lượt tô màu~;~
• Dòng cuối cùng chứa ~N~ số nguyên là số hiệu màu của từng ô vuông sau khi các bạn đã tô màu.

Kết quả ghi ra tệp văn bản COLOR.OUT:

Một dòng gồm ~M~ số nguyên là thứ tự tô màu để thu được dãy ô vuông khi trò chơi kết thúc. Có thể có bạn ghi nhầm thông tin lượt tô màu của mình nên không tìm được cách chọn thì in ra ~−1~. Nếu có nhiều cách chọn thì in ra cách bất kì.

Ràng buộc

• Có ~20\%~ số test ứng với ~1 ≤ N, M ≤ 9;~
• ~20\%~ số test khác ứng với ~1 ≤ N, M ≤ 5000~ và màu của mỗi lần tô là khác nhau~;~
• ~20\%~ số test khác ứng với ~1 ≤ N, M ≤ 5 \times 10^5~ và màu của mỗi lần tô là khác nhau~;~
• ~20\%~ số test khác ứng với ~1 ≤ N, M ≤ 5000;~
• ~10\%~ số test khác ứng với ~1 ≤ N, M ≤ 5 \times 10^5~ và ~1 ≤ C_i ≤ 5;~
• ~10\%~ số test còn lại không có điều kiện gì thêm.

Ví dụ

Input

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

Output

4 5 3 1 2