Bài tập

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

Một công ty công nghệ có \(N\) phòng ban được tổ chức theo dạng cấu trúc cây, với phòng ban số \(1\) là gốc của cây. Mỗi phòng ban tương ứng với một đỉnh của cây. Phòng ban \(i\) có hai thông số đặc trưng:

• \(a(i)\): Loại hình hoạt động chính của phòng ban.
• \(b(i)\): Số điểm tài nguyên mà phòng ban có được.

Giám đốc điều hành muốn tối ưu hóa hiệu suất làm việc của từng phòng ban. Nhiệm vụ là, với mỗi phòng ban \(i\), hãy tìm giá trị \(f(u, v)\) lớn nhất giữa hai phòng ban \(u\) và \(v\) nằm trong cây con có gốc là phòng ban \(i\), sao cho phòng ban \(i\) là tổ tiên chung gần nhất của \(u\) và \(v\). Giá trị \(f(u, v)\) được định nghĩa như sau:

$
f(u, v) =
\begin{cases}
0 & \text{nếu } a(u) \neq a(v), \
\sum b(x) & \text{với } x \text{ là các phòng ban nằm trên đường đi từ } u \text{ đến } v.
\end{cases}
$

Lưu ý:

• \(lca(u, v) = i\) khi và chỉ khi phòng ban \(i\) là tổ tiên chung gần nhất và là tổ tiên sâu nhất của cả hai phòng ban \(u\) và \(v\).
• Đường đi từ \(u\) đến \(v\) bao gồm tất cả các phòng ban trên cây từ \(u\) đến \(v\).

Input

• Dòng đầu tiên chứa số nguyên \(N\) \((1 \leq N \leq 10^5)\), số lượng đỉnh trong cây.
• Dòng thứ hai chứa \(N\) số nguyên \(a(1), a(2), \ldots, a(N)\) \((1 \leq a(i) \leq 10^9)\).
• Dòng thứ ba chứa \(N\) số nguyên \(b(1), b(2), \ldots, b(N)\) \((0 \leq b(i) \leq 10^9)\).
• \(N-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) \((1 \leq u, v \leq N)\), biểu diễn cạnh nối giữa hai đỉnh \(u\) và \(v\) trong cây.

Output

Với mỗi \(i\) \((1 \leq i \leq N)\), hãy tìm giá trị lớn nhất của \(f(u, v)\) với \(u, v\) là hai phòng ban nằm trong cây con có gốc tại \(i\).

Example

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

17 0 16 0 0 0 0 0 

Scoring

• Có \(30\%\) số test ứng với \(n \le 1000\)
• Có \(20\%\) số test ứng với \(a(i) \le 10\)
• \(50\%\) số test còn lại không có ràng buộc gì thêm.

Trong một ngôi làng nhỏ, có một truyền thuyết về hai con số kỳ diệu \(a\) và \(b\), được gọi là cặp số LTN. Theo truyền thuyết, cặp số này thỏa mãn điều kiện:

với \(X\) là một số nguyên dương được các trưởng làng lựa chọn cẩn thận.

Một ngày nọ, Eldric - cậu bé thông minh nhất làng - được giao nhiệm vụ giải mã bài toán LTN. Eldric cần phải tìm ra tất cả các cặp số \(a, b\) là cặp số LTN thỏa mãn điều kiện trên. Tuy nhiên, với số \(X\) lớn, nhiệm vụ này không hề dễ dàng.

\textbf Yêu cầu: Hãy giúp Eldric xác định có bao nhiêu cặp số \((a, b)\) thỏa mãn điều kiện của một cặp số LTN.

Input

• Dòng đầu tiên chứa một số nguyên \(T\) \((1 \leq T \leq 10^5)\), là số lượng bộ test.
• \(T\) dòng tiếp theo, mỗi dòng chứa một số nguyên \(X\) \((1 \leq X \leq 10^6)\).

Output

• \(30\%\) số điểm ứng với \(1 \leq T \leq 10^3\), \(1 \leq X \leq 100\).
• \(30\%\) số điểm ứng với \(1 \leq T \leq 10^3\), \(1 \leq X \leq 10^6\).
• \(40\%\) số điểm còn lại không có ràng buộc gì thêm.

Example

1
2

6