Bài toán tìm ước chung lớn nhất và tìm bội chung nhỏ nhất của 2 số nguyên dương là bài toán quen thuộc khi học số học lớp 6. Cho biết ~M~ là ước chung lớn nhất ~2~ số nguyên dương, ~N~ là bội chung nhỏ nhất của ~2~ số nguyên dương.

Yêu cầu: Tìm ~2~ số nguyên dương ~a~ và ~b~ có tổng nhỏ nhất sao cho ước chung lớn nhất của ~a~ và ~b~ bằng ~M~, bội chung nhỏ nhất của ~a~ và ~b~ bằng ~N~.

Input

• Gồm một dòng duy nhất là hai số nguyên dương ~M~ và ~N~ (~1 \le N \le M \le 10^6)~.

Output

• Gồm một dòng duy nhất là hai số nguyên dương ~a~ và ~b~ ~(a \le b)~.

Sample Tests

Input

4 60

Output

12 20

Trong một cơ quan, có ~𝑁~ yêu cầu sử dụng phòng họp trực tuyến. Cơ quan đã đăng kí với cấp trên đường truyền ưu tiên theo ~𝑀~ mốc thời gian được đánh số từ ~1~ đến ~M~. Mỗi yêu cầu đăng kí sử dụng phòng họp trong các mốc thời gian liên tiếp từ ~𝐿~ đến ~𝑅~ ~(1 ≤ 𝐿 ≤ 𝑅 ≤ 𝑀)~. Để tiện cho việc sắp xếp và phục vụ các phòng họp, cần biết mỗi yêu cầu xung đột với bao nhiêu yêu cầu khác (hai yêu cầu gọi là xung đột với nhau nếu có chung ít nhất một mốc thời gian).

Yêu cầu: Cho biết ~𝑁~ yêu cầu sử dụng phòng họp. Với mỗi yêu cầu, hãy tính số lượng yêu cầu xung đột với nó.

Dữ liệu nhập vào từ file văn bản XPH.INP:

• Dòng đầu chứa số hai nguyên ~𝑁,𝑀~ ~(1 ≤ 𝑁 ≤ 2 \times 10^5; \ 1 ≤ 𝑀 ≤ 10^9)~ là số lượng yêu cầu và số lượng mốc thời gian~;~
• ~N~ dòng tiếp theo, dòng thứ ~𝑖~ chứa hai số nguyên ~𝐿_i,𝑅_i \ (1 ≤ 𝐿_i ≤ 𝑅_i ≤ 𝑀; \ 1 ≤ 𝑖 ≤ 𝑁)~ là mốc thời gian bắt đầu và kết thúc của yêu cầu thứ ~𝑖~.

Kết quả ghi ra file văn bản XPH.OUT:

Gồm ~𝑁~ dòng, dòng thứ ~𝑖~ mô tả số lượng yêu cầu xung đột với yêu cầu thứ ~𝑖~ ~(1 ≤ 𝑖 ≤ 𝑁)~.

Ràng buộc

• Có ~25\%~ số test ứng với ~25\%~ số điểm của bài thoả mãn: ~𝑁, 𝑀 ≤ 400;~
• ~25\%~ số test khác ứng với ~25\%~ số điểm của bài thoả mãn: ~𝑁 ≤ 2000;~
• ~25\%~ số test khác ứng với ~25\%~ số điểm của bài thoả mãn: ~𝑀 ≤ 4 \times 10^5;~
• ~25\%~ số test còn lại ứng với ~25\%~ số điểm của bài không có ràng buộc gì thêm.

Ví dụ

Input

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

Output

1
3
2
0
2

Cân nặng đã ở mức đáng báo động, ~K~ quyết định tập chạy để giảm cân. Khu vực ~K~ sống có một con đường dài, điểm đầu của con đường là điểm ~0~, điểm cuối của con đường là điểm ~N - 1~. Các điểm cách đều nhau một khoảng ~1~ đơn vị độ dài, điểm thứ ~i~ có độ cao ~H_i~. ~K~ muốn chọn ra một đoạn đường để tập chạy sao cho:

• Đoạn đường có chiều dài ít nhất là ~L~,
• Chênh lệch độ cao giữa điểm cao nhất và điểm thấp nhất trên đoạn đường không vượt quá ~D~.

Bạn hãy giúp xác định xem có bao nhiêu đoạn đường thỏa mãn.

Input

• Dòng đầu tiên ghi ba số ~N, L, D~.
• Dòng thứ hai ghi ~N~ số ~H_i~ là độ cao của điểm thứ ~i~.

Output

• In ra số đoạn đường thỏa mãn.

Constraints

• ~1 \leq L < N \leq 10^6~
• ~0 \leq D \leq 10^4~
• ~1 \leq H_i \leq 10^4~

Sample Test

Input

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

Output

5

~A~ là một người rất thông minh. Anh đã xuất sắc hoàn thành tốt phần thi của mình trong trò chơi mà ban tổ chức ~X~ đề ra. Để quyết định giá trị phần thưởng của mình, ban tổ chức quyết định tạo ra một trò chơi phụ dành cho ~A~. Trò chơi của ~A~ có tên là xóa dãy. Trò chơi sẽ có một dãy nhị phân ~s~ gồm ~n~ phần tử và một dãy số ~D~ gồm ~n~ phần tử. Nhiệm vụ của ~A~ đó là xoá dãy nhị phân trên theo quy luật sau:

• Tại mỗi bước chơi, chọn xoá ~x~ phần tử liền kề giống nhau trong dãy nhị phân ~s~ ( ~x < |s|~).Ví dụ : ~1(00)1101 \rightarrow 11101~.
• Số điểm nhận được là ~D_x~.
• Trò chơi sẽ tiếp tục cho đến khi dãy ~s~ hết phần tử.
• Điểm càng cao thì giá trị phần thưởng càng lớn

~A~ thực sự đã rất mệt trong phần thi trước đấy của mình nhưng anh cũng muốn giành được số điểm cao nhất để lấy có được phần thưởng lớn nhất. ~A~ rất cần đến sự giúp đỡ của các bạn học sinh. Hãy giúp đỡ ~A~ nhé!

Yêu cầu:

• In ra số điểm cao nhất mà ~A~ có thể đạt được sau phần chơi.

Input

• Dòng thứ nhất là số ~n~.
• Dòng thứ hai là dãy nhị phần có ~n~ phần tử gồm các số ~0~ và ~1~.
• Dòng thứ ba là dãy số ~D~.

Output

• In ra kết quả bài toán.

Subtasks

• Subtask ~1~ (~30 \%~ số điểm):​ ~n ≤ 9~
• Subtask ~2~ (~50 \%~ số điểm):​ ~n ≤ 100~
• Subtask ~3~ (~20 \%~ số điểm):​ ~n ≤ 1000~, cả dãy ~s~ chỉ bao gồm ~1~ giá trị

Sample Test

Sample Input

5
10101
3 10 15 15 15

Sample Output

23

Note

~10(1)01→1(00)1→~(11)~→∅~

Công ty Long Vân giới thiệu siêu máy tính có khả năng thực hiện được tỉ tỉ phép toán trong vòng một giây. Để chứng minh sức mạnh của siêu máy tính, công ty đã cho máy tính thực hiện một số lượng rất lớn các thao tác như sau:

• Ban đầu, dãy ~S~ không có phần tử nào;
• Có ~t~ thao tác, thao tác thứ ~i \ (i=1,2,\cdots,t)~ thuộc một trong các loại:
  • ~1~: Thêm vào dãy ~𝑆~ một phần tử mới ~x_i~;
  • ~2~: Tính tổng các phần tử của dãy ~𝑆~ hiện tại có giá trị nằm trong đoạn ~[a_i, b_i]~;
  • ~3~: Sắp xếp dãy ~S~ hiện tại theo thứ tự không giảm rồi tính tổng tất cả các phần tử có thứ tự từ ~p_i~ đến ~q_i~ (~1 \le p_i \le q_i \le |S|~, trong đó ~|S|~ là số lượng phần tử của dãy ~S~ hiện tại). Sau đó, chèn vào dãy ~S~ hai phần tử, một phần tử có giá trị bằng phần tử có thứ tự ~p_i~ cộng với ~1~ và phần tử có giá trị bằng phần tử có thứ tự ~q_i~ trừ đi ~1~.

Công ty sẽ trao thưởng cho người nào kiểm chứng được kết quả mà siêu máy tính đưa ra. Bạn được cho dãy gồm ~t~ thao tác, với mỗi thao tác loại ~2~ và ~3~ hãy đưa câu trả lời tương ứng.

Input

• Dòng đầu chứa số nguyên dương ~t~;
• Dòng thứ ~i~ trong ~t~ dòng tiếp theo mô tả thao tác thứ ~i~ là một trong ba loại thao tác theo khuôn dạng: Bắt đầu số ~k_i~ (~k_i~ bằng ~1~ hoặc ~2~ hoặc ~3~).
  • Nếu là thao tác loại ~1~ thì tiếp theo là một số nguyên ~x_i~ (~-10^9 \le x_i \le 10^9~),
  • Nếu là thao tác loại ~2~ thì tiếp theo là hai số nguyên ~a_i, b_i~ (~-10^9 \le a_i \le b_i \le 10^9~),
  • Nếu là thao tác loại ~3~ thì tiếp theo là hai số nguyên dương ~p_i, q_i~ (~1 \le p_i \le q_i \le |S|~).

Output

• Gồm một số dòng, mỗi dòng chứa một số lần lượt là các câu trả lời cho các thao tác loại ~2, 3~ theo thứ tự xuất hiện ở dữ liệu vào.

Subtasks

• Subtask ~1~ (~40\%~ số điểm): ~t \le 10^3~
• Subtask ~2~ (~40\%~ số điểm): ~t \le 10^5~ và không có thao tác loại 3
• Subtask ~3~ (~20\%~ số điểm): ~t \le 10^5~.

Sample Test

Sample Input

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

Sample Output

3
5
10

Note

S = ()
S = (5)
S = (5,3)
S = (5,3,1)
Đưa ra 3
S = (5,3,1,2)
S = (1,2,3,5), đưa ra 5, S = (1,2,3,5,3,2)
Đưa ra 10

Một đất nước có ~N~ thành phố được đánh số từ ~1~ đến ~N~ và có ~N-1~ đường cao tốc hai chiều. Mọi cặp thành phố đều có thể đi được đến nhau khi sử dụng các đường cao tốc này.

Khoảng cách giữa hai thành phố ~x~ và ~y~ là số đường cao tốc cần phải đi qua ít nhất để đi từ thành phố ~x~ đến thành phố ~y~.

Chính phủ quyết định sẽ phá một đường cao tốc và xây một cái cao tốc mới sao cho khoảng cách xa nhất giữa hai thành phố là lớn nhất.

Hãy tìm khoảng cách lớn nhất đó.

Input

• Dòng đầu gồm số nguyên dương ~N~ (~3 \le N \le 3 \times 10^5~).
• ~N - 1~ dòng tiếp theo, mỗi dòng gồm hai số nguyên dương ~u, v~ thể hiện có một đường đi hai chiều giữa hai thành phố ~u~ và thành phố ~v~ (~1 \le u, v \le N~).

Output

• Gồm một dòng duy nhất là kết quả bài toán.

Subtask

Example

Sample Input

4
1 2 
1 3
3 4

Sample Output

3