Bài tập

Trên một vùng đất rộng lớn được xem như một mặt phẳng tọa độ có góc là \((0,0)\), người ta thực hiện nhiều chiến dịch phun thuốc trừ sâu. Mỗi chiến dịch sẽ phun thuốc lên một mảnh đất hình chữ nhật, được xác định bởi hai đỉnh đối diện là \((x_1, y_1)\) và \((x_2, y_2)\) (các cạnh song song với trục tọa độ).

Mỗi lần phun thuốc, tất cả các ô nằm trong phạm vi hình chữ nhật sẽ tăng thêm đúng \(1\) đơn vị thuốc.

Một ô là đạt chuẩn nếu lượng thuốc tại ô đó nằm trong đoạn \([L,R]\).

Hãy tính số ô đạt chuẩn sau tất cả các chiến dịch phun thuốc.

Input

• Dòng đầu tiên chứa ba số nguyên \(N\), \(L\), \(R\) --- số lượng chiến dịch phun thuốc, ngưỡng an toàn dưới và trên (\(1 \leq N \leq 10^5\), \(0 \leq L \leq R \leq N\)).
• \(N\) dòng tiếp theo, mỗi dòng chứa bốn số nguyên \(x_1, y_1, x_2, y_2\) (\(0 \leq x_1 \leq x_2 \leq 10^5\), \(0 \leq y_1 \leq y_2 \leq 10^5\)) --- mô tả phạm vi phun thuốc của chiến dịch thứ \(i\).

Output

In ra một số nguyên duy nhất là số ô đạt chuẩn.

Example

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

25

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

43

Scoring

\begintabular|c|c|l|
\hline
Subtask & Điểm & Giới hạn

\hline
1 & 8 & \(N \le 200\), \(0 \le x_1 \le x_2 \le 200\), \(0 \le y_1 \le y_2 \le 200\)

\hline
2 & 12 & \(0 \le x_1 \le x_2 \le 2000\), \(0 \le y_1 \le y_2 \le 2000\)

\hline
3 & 10 & \(L = 1\), \(R = N\)

\hline
4 & 20 & \(L = R = N\)

\hline
5 & 15 & \(L = R\)

\hline
6 & 15 & \(N \le 10^4\)

\hline
7 & 20 & Không có ràng buộc bổ sung

\hline
\endtabular

Cây là đồ thị vô hướng liên thông không có chu trình. Bài toán này cho một cây không có gốc.
Lá của cây là đỉnh chỉ kết nối với nhiều nhất một đỉnh khác.

Quân là một thợ mộc lành nghề, đến nay tuổi nghề cũng đã được 16 năm. Hiện tại, Quân vừa mới đi rừng về, đào được một cái cây có \(n\) đỉnh. Giờ Quân muốn xử lí cái cây này. Để làm điều đó, trong một thao tác, Quân loại bỏ tất cả các lá của cây.

Ví dụ ta có một cây như sau:

\begincenter

\endcenter

Sau một thao tác:

\begincenter

\endcenter

Chú ý một số trường hợp đặc biệt sau:

• nếu cây không có đỉnh nào thì thao tác nào cũng không thay đổi cây

• nếu cây còn duy nhất một đỉnh thì đỉnh đấy sẽ bị loại bỏ

• nếu cây còn lại hai đỉnh thì hai đỉnh đấy đồng thời bị loại bỏ.

Quân liên tục thực hiện thao tác như vậy đúng \(k\) lần. Hỏi, sau \(k\) thao tác, cây còn lại bao nhiêu đỉnh ?

Input

Dòng đầu tiên gồm 2 số \(n, k\) - số lượng đỉnh của cây và số lượng thao tác.

\(n - 1\) dòng tiếp theo, mỗi dòng chứa \(2\) số mô tả cạnh của cây.

Output

Một dòng, kết quả bài toán

Example

14 1
1 2
2 3
2 4
4 5
4 6
2 7
7 8
8 9
8 10
3 11
3 12
1 13
13 14

7

Scoring

Có 30 phần trăm số test có \(n, k <= 10^3\)

Có 20 phần trăm số test cây có dạng đường thẳng.

50 phần trăm số test còn lại \(n, k <= 4.10^5\)

Cho mảng \(A\) gồm \(n\) phần tử. Một dãy con của \(A\) là một dãy thu được bằng cách chọn một số phần tử theo thứ tự tăng dần chỉ số (không nhất thiết liên tiếp).
Yêu cầu: đếm số dãy con khác nhau và khác rỗng của \(A\).

\InputFile

• Dòng đầu gồm số nguyên \(n\) (\(1 \le n \le 10^6\)).
• Dòng thứ hai gồm \(n\) số nguyên \(A_i\) (\(1 \le A_i \le 10^6\)).

\OutputFile
In ra số lượng dãy con khác nhau, modulo \(123456789\).

Example

3
1 2 1

6

Trong giờ học Vật lý, một thành viên của CLB CHTCoder đang lơ đãng nhớ về crush thì bị thầy phát hiện.

Để không bị trừ điểm hoặc ghi vào sổ đầu bài, thầy đã giao cho hai bạn một thử thách:
Cho một bảng kích thước \(n \times n\), trong đó các số được điền theo thứ tự tăng dần từ trái sang phải và từ trên xuống dưới, bắt đầu từ \(1\) cho tới \(n \times n\).

Yêu cầu của thầy rất đơn giản: Tính tổng các phần tử nằm trên đường chéo chính của bảng.

Input

Đọc từ file NHOEM.INP:

• Số nguyên dương \(t\) (\(1 \le t \le 10^{6}\)) --- số câu hỏi.
• Mỗi dòng tiếp theo chứa một số nguyên dương \(n\) (\(1 \le n \le 10^{6}\)).

Output

Ghi ra file NHOEM.OUT:

• Gồm \(t\) dòng, mỗi dòng là tổng đường chéo chính tương ứng.

Example

2
3
6

15
111

Scoring

• Subtask 1 (70%): \(1 \le t, n \le 10^{3}\).
• Subtask 2 (30%): Không có ràng buộc thêm.