Bài tập

Trong tương lai xa tại hành tinh Binance, Liên minh Thiên hà đã xây dựng một hệ thống mạng lượng tử kết nối \(n\) trạm truyền tin liên hành tinh, các trạm truyền tin được đánh số liên tiếp từ \(1\) đến \(n\) \((1 \leq n \leq 10^5)\). Có \(n - 1\) liên kết kết nối giữa các cặp trạm truyền tin, liên kết thứ \(i\) sẽ kết nối hai trạm truyền tin \(u_i\) và \(v_i\) \((1 \leq u_i \neq v_i \leq n)\), liên kết này có giới hạn băng thông là \(w_i\) \((1 \leq w_i \leq 10^9)\). Hệ thống được thiết kế như một đồ thị cây, nghĩa là giữa bất kỳ hai trạm bất kỳ luôn tồn tại đúng một tuyến truyền dữ liệu duy nhất.

Khi truyền dữ liệu giữa hai trạm bất kỳ, giới hạn của đường truyền được xác định là giá trị nhỏ nhất trong tất cả các giới hạn băng thông trên đường đi.

Một mạng con Binance được định nghĩa là một nhóm các trạm mạng trên hệ thống. Mạng con, nói một cách cụ thể hơn, là mạng bao gồm các trạm truyền tin \(k_1, k_2, k_3, ..., k_m\) (với \(m\) là số lượng trạm truyền tin trong mạng). Để xác thực dữ liệu một cách mạnh mẽ nhất, các nhà khoa học muốn tìm ra cặp trạm \((k_i, k_j)\) trong mạng con sao cho đường truyền giữa chúng có giới hạn là lớn nhất trong tất cả các cặp --- gọi đó là đường kính của mạng Binance.

Để đánh giá được chất lượng của toàn bộ \(n\) trạm truyền tin trong mạng, ban đánh giá của mạng con này sẽ đưa ra \(Q\) phép thử, mỗi phép thử thứ \(i\) gồm \(m\) trạm truyền tin \(k_1, k_2, ..., k_m\). Với mỗi phép thử, bạn hãy tính toán đường kính của mạng con được cho.

Nhiệm vụ của bạn: Với mỗi mạng con Binance, hãy giúp họ xác định đường kính của mạng con này.

Input

• Dòng đầu chứa số nguyên \(n\) --- số trạm mạng \((1 \leq n \leq 10^5)\).
• \(n-1\) dòng tiếp theo, mỗi dòng gồm 3 số nguyên \(u_i, v_i, w_i\) --- mô tả kết nối trực tiếp giữa trạm \(u_i\) và \(v_i\) với giới hạn truyền tải \(w_i\) \((1 \leq u_i \neq v_i \leq n, 1 \leq w_i \leq 10^9)\).
• Dòng tiếp theo chứa số nguyên \(Q\) --- số phép thử cần xử lí \((1 \leq Q \leq 10^5)\).
• \(Q\) dòng tiếp theo, mỗi dòng có dạng \(m\ k_1\ k_2\ \dots\ k_m\) --- mô tả một mạng con gồm \(m\) trạm \((2 \leq m \leq n)\).

Output

Với mỗi truy vấn, in ra một dòng duy nhất là đường kính xác thực của mạng Binance tương ứng.

Example

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

4
1
5
3

Scoring

Gọi \(T\) là tổng số lượng đỉnh trong tất cả \(Q\) phép thử.

• Có \(10\%\) số test tương ứng với \(10\%\) số điểm có \(n, T \leq 100, Q = 1, m = n\), các trạm truyền tin trong phép thử đầu tiên là \(n\) trạm truyền tin trong đồ thị Binance.
• Có \(10\%\) số test tương ứng với \(10\%\) số điểm có \(n, T \leq 10^5, Q = 1, m = n\), các trạm truyền tin trong phép thử đầu tiên là \(n\) trạm truyền tin trong đồ thị Binance.
• Có \(20\%\) số test tương ứng với \(20\%\) số điểm có \(n, T, Q \leq 100\).
• Có \(20\%\) số test tương ứng với \(20\%\) số điểm có \(n, T, Q \leq 1000\).
• Có \(20\%\) số test tương ứng với \(20\%\) số điểm \(n, T, Q \leq 10^5\), mỗi trạm truyền tin chỉ liên kết tối đa với \(2\) trạm truyền tin khác.
• Có \(20\%\) số test tương ứng với \(20\%\) số điểm còn lại không có ràng buộc gì thêm.

Putata đang chơi một trò chơi rắn nổi tiếng trên máy tính xách tay của mình, trong đó con rắn di chuyển trên một bàn cờ kích thước \(n \times m\). Trên bàn cờ này có thể có một số ô chứa chướng ngại vật. Con rắn có thể được biểu diễn như một dãy các cặp tọa độ xác định vị trí của thân nó: \((x_1, y_1), (x_2, y_2), \dots, (x_k, y_k)\). Ở đây, \(k\) là độ dài của con rắn. Đầu của con rắn là tại \((x_1, y_1)\), đuôi là tại \((x_k, y_k)\), và các phần thân liền kề sẽ nằm trên các ô liền kề nhau theo cạnh.

Trong trò chơi này, con rắn sẽ được điều khiển bằng một chuỗi các lệnh di chuyển. Có 5 loại lệnh mà bạn có thể sử dụng:

• L: Di chuyển con rắn một ô sang trái. Đầu của con rắn sẽ di chuyển tới \((x_1, y_1 - 1)\).
• R: Di chuyển con rắn một ô sang phải. Đầu của con rắn sẽ di chuyển tới \((x_1, y_1 + 1)\).
• U: Di chuyển con rắn một ô lên trên. Đầu của con rắn sẽ di chuyển tới \((x_1 - 1, y_1)\).
• D: Di chuyển con rắn một ô xuống dưới. Đầu của con rắn sẽ di chuyển tới \((x_1 + 1, y_1)\).
• S: Rút ngắn chiều dài của con rắn đi một đơn vị. Đuôi của con rắn sẽ bị xóa đi, độ dài của con rắn sẽ trở thành \(k - 1\). Lưu ý rằng bạn không thể thực hiện lệnh này khi \(k = 1\).

Khi đầu của con rắn di chuyển, mỗi phần thân của nó cũng sẽ di chuyển theo. Cụ thể, phần thân thứ \(i\) \((2 \leq i \leq k)\) sẽ di chuyển đến vị trí mà phần thân thứ \((i-1)\) ở đó trước khi lệnh được thực hiện. Con rắn không thể di chuyển vào một ô có chướng ngại vật, và không thể di chuyển ra ngoài bàn cờ. Ngoài ra, con rắn không được tự va vào thân của nó, nghĩa là không được có hai phần của thân nằm trên cùng một vị trí.

Trường hợp đặc biệt

Xem xét trường hợp đặc biệt sau: Đầu của con rắn ở vị trí \((x_1, y_1)\), và đuôi ở vị trí \((x_k, y_k)\). Nếu đầu của con rắn đang di chuyển đến \((x'_1, y'_1) = (x_k, y_k)\), thì được phép hoán đổi vị trí đầu và đuôi của con rắn bằng một lệnh duy nhất khi \(k = 2\).

Yêu cầu

Bạn sẽ được cung cấp bản đồ của bàn cờ và vị trí của thân con rắn. Gọi \(f(i, j)\) là số lệnh tối thiểu để đầu của con rắn có thể đến vị trí \((i, j)\), hoặc \(0\) nếu không thể. Nhiệm vụ của bạn là tính giá trị sau:

$
\left( \sum_{i=1}^n \sum_{j=1}^m f(i, j)^2 \right) \mod 2^{32}.
$

Input

• Dòng đầu tiên chứa ba số nguyên \(n\), \(m\) và \(k\) \((1 \leq n, m \leq 3000, 1 \leq k \leq \min\{nm, 10^5\})\) - kích thước của bàn cờ và độ dài của con rắn.
• Trong \(k\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(x_i\) và \(y_i\) \((1 \leq x_i \leq n, 1 \leq y_i \leq m, |x_i - x_{i+1}| + |y_i - y_{i+1}| = 1)\) biểu thị vị trí của phần thân thứ \(i\) của con rắn. Đảm bảo rằng tất cả các cặp tọa độ \((x_i, y_i)\) là khác nhau và không có phần thân nào nằm trên ô chứa chướng ngại vật.
• Trong \(n\) dòng tiếp theo, dòng thứ \(i\) chứa một chuỗi có độ dài \(m\). Nếu ô \((i, j)\) trống, ký tự thứ \(j\) trong dòng thứ \(i\) là '.'. Nếu ô \((i, j)\) chứa chướng ngại vật, ký tự đó là '#'.

Output

In ra một số nguyên không âm là đáp án cho bài toán.

Example

4 5 5
3 5
3 4
3 3
3 2
4 2
.....
.....
.....
.....

293

2 2 4
1 1
1 2
2 2
2 1
..
..

14

5 5 3
1 2
1 1
2 1
.....
.###.
.#.#.
.###.
.....

407

Scoring

• Có \(25\%\) số test có \(n, m, k \leq 5\).

• Có \(25\%\) số test có \(k = 2\).

• Có \(25\%\) số test có \(n, m \leq 300\), \(2 < k \leq 5\).

• \(25\%\) số test còn lại không có ràng buộc gì thêm.

Thành phố Quân sống là một thành phố có \(n\) quận và có \(n - 1\) con đường có trọng số nối giữa hai thành phố khác nhau, sao cho từ thành phố bất kì có thể đi sang tất cả các thành phố khác. Khi tận thế đến, có tất cả \(n - 1\) thiên thạch rơi lần lượt vào \(n - 1\) con đường theo từng thời điểm, thời điểm \(i\) thiên thạch thứ \(i\) sẽ phá hủy con đường có trọng số nhỏ nhất trong các con đường chưa bị phá hủy.

Yêu cầu : Ngay sau thời điểm thứ \(i\), có bao nhiêu cặp thành phố có thể đi lại với nhau (nói cách khác, đếm số cặp \((u, v)\) \((u < v)\), sao cho tồn tại một con đường nối giữa \(u\) và \(v\)).

Input

Dòng thứ nhất là số nguyên dương \(n\) là số thành phố \((n \leq 500000)\).

\(n - 1\) dòng tiếp theo gồm ba số \(u, v, w\) mô tả đường đi và trọng số của đường đi \((u, v \leq n, w \leq 10^9)\)

Đảm bảo trọng số của các cạnh là đôi một phân biệt.

Output

Gồm một dòng chứa \(n - 1\) số, mỗi số cách nhau một dấu cách, số thứ \(i\) mô tả kết quả ngay sau thời điểm thứ \(i\).

Example

4
1 2 3
1 3 2
1 4 1

3 1 0 

Scoring

\(20\%\) số điểm có \(n \leq 100\)

\(30\%\) số điểm có \(n \leq 1000\)

\(50\%\) số điểm còn lại không có ràng buộc gì thêm.

Cho \(n\) hình chữ nhật song song với trục tọa độ.
Hình chữ nhật thứ \(i\) được mô tả bởi bốn số nguyên \((x_1, y_1, x_2, y_2)\) với \(x_1 < x_2\) và \(y_1 < y_2\),
tương ứng với hai đỉnh đối diện \((x_1,y_1)\) và \((x_2,y_2)\).

Hãy tính diện tích của hợp của \(n\) hình chữ nhật.

\InputFile

• Dòng đầu tiên chứa số nguyên \(n\).

• \(n\) dòng tiếp theo, mỗi dòng gồm bốn số nguyên \(x_1, y_1, x_2, y_2\).

\OutputFile
In ra một số nguyên duy nhất là diện tích hợp của các hình chữ nhật.

Điều kiện

• \(1 \le n \le 2 \cdot 10^5\).
• \(|x_1|,|x_2|,|y_1|,|y_2| \le 10^9\).
• \(x_1 < x_2,\ y_1 < y_2\).

Example

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

9