Bài tập

Cho một cây có \(n\) đỉnh, được đánh số từ \(1\) đến \(n\). Nhiệm vụ của bạn là xử lý \(q\) truy vấn. Mỗi truy vấn yêu cầu tính số lượng đỉnh chung giữa hai đường đi trong cây.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\) \((1 \leq n \leq 2 \times 10^5, 1 \le q \le 10^5)\) -- số đỉnh của cây và số lượng truy vấn.
• \(n-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(a\) và \(b\) \((1 \leq a, b \leq n)\) -- biểu thị một cạnh nối giữa hai đỉnh \(a\) và \(b\).
• \(q\) dòng cuối cùng mô tả các truy vấn, mỗi truy vấn có dạng A B C D, \((1 \leq A, B, C, D \leq n)\). Yêu cầu: Tìm số lượng đỉnh chung giữa đường đi từ \(A\) đến \(B\) và đường đi từ \(C\) đến \(D\).

Output

• Với mỗi truy vấn, in ra một số nguyên trên một dòng duy nhất biểu thị số lượng đỉnh chung giữa hai đường đi được chỉ định.

Example

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

1

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

0
4
0
3

Cho dãy \(a\) gồm \(n\) phần tử. Đoạn \([l, r]\) của dãy \(a\) là dãy gồm các phần tử liên tiếp \(a_l, a_{l+1}, \ldots, a_r\).

Độ xấu của đoạn \([l, r]\) được định nghĩa là số lượng chỉ số \(i\) thỏa mãn \(l \le i \le r\) sao cho \(a_i \ne i - l + 1\).

Hãy chia dãy \(a\) thành một số đoạn (không giao nhau, mỗi phần tử thuộc đúng một đoạn) sao cho tổng độ xấu của tất cả các đoạn là nhỏ nhất.

Input

• Dòng đầu tiên chứa số nguyên \(n\) \((1 \le n \le 2 \times 10^5)\) --- độ dài của dãy \(a\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) \((1 \le a_i \le n)\) --- các phần tử của dãy.

Output

• In ra một số nguyên duy nhất --- tổng độ xấu nhỏ nhất có thể đạt được sau khi chia dãy thành các đoạn.

Example

5
2 1 3 2 1

2

Scoring

• Subtask 1 (25 điểm): \(n \le 200\)
• Subtask 2 (25 điểm): \(n \le 3000\)
• Subtask 3 (25 điểm): \(a_i \le 200\)
• Subtask 4 (25 điểm): Không có ràng buộc bổ sung

Cho \(n\) điểm nguyên trên mặt phẳng tọa độ hai chiều.

Có \(q\) truy vấn dạng \((x, y, d)\). Mỗi truy vấn xác định một tam giác vuông cân có ba đỉnh là

Hãy đếm số lượng điểm trong \(n\) điểm đã cho nằm bên trong hoặc trên cạnh của tam giác này.

\InputFile
Dòng đầu tiên gồm hai số nguyên \(n, q\).

\(n\) dòng tiếp theo, mỗi dòng gồm hai số nguyên \(x, y\) mô tả một điểm \((x,y)\).

\(q\) dòng tiếp theo, mỗi dòng gồm ba số nguyên \(x, y, d\) mô tả một truy vấn.

\OutputFile
In ra \(q\) dòng, dòng thứ \(i\) là đáp án của truy vấn thứ \(i\).

Điều kiện

• \(1 \le n, q \le 10^5\).
• \(1 \le x, y \le 10^5\) đối với các điểm.
• \(1 \le x, y, d \le 10^5\) đối với truy vấn.

Example

2 2
3 3
3 4
1 1 3
2 2 3

0
2

Cây là một đơn đồ thị vô hướng liên thông không có chu trình. Giữa hai đỉnh \(x\), \(y\) trên cây, luôn luôn tồn tại và duy nhất một đường đi đơn giữa chúng.

Cho một cây với các cạnh có trọng số không âm. Ta gọi khoảng cách giữa hai đỉnh là tổng xor (hay tổng nim) của các trọng số các cạnh trên đường đi đơn giữa hai đỉnh đó. Lưu ý là cặp \((x, y)\) và \((y, x)\) được coi là một cặp

Yêu cầu: Hãy tính tổng khoảng cách của tất cả các cặp đỉnh trên cây.

Input

• Dòng đầu ghi số nút của cây: \(n\)

• \(n - 1\) dòng tiếp theo, mỗi dòng ghi một cạnh của cây: \(u, v, L (1 ≤ u, v ≤ n)\)

Output

In ra một số nguyên là kết quả bài toán

Example

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

34

Scoring

• Trong tất cả các test: \(1 ≤ n ≤ 10^5 , 0 ≤ L ≤ 10^9\)

• Có \(20\%\) số test với \(n ≤ 5000\)

• Có \(30\%\) số test với mỗi đỉnh đều kề với nhiều nhất 2 đỉnh khác

• Có \(50\%\) số test với ràng buộc gốc