Bài tập

Đất nước \(Z\) có \(n\) thành phố, các thành phố được đánh số từ \(1\) đến \(n\) . Có đúng \(n - 1\) con đường hai chiều nối giữa các thành phố thỏa mãn điều kiện: có thể đi từ thành phố bất kì đến tất cả các thành phố còn lại theo đường trực tiếp hoặc gián tiếp qua các thành phố khác. Đất nước \(Z\) thường có các
sự kiện văn hóa lớn, mỗi lần sự kiện sẽ được tổ chức tại một thành phố, điều này ảnh hưởng tới chi phí di chuyển trên các con đường. Cụ thể, nếu thành phố \(u\) là thành phố tổ chức sự kiện văn hóa, khi đó các con đường hướng tới thành phố \(u\) sẽ có chi phí là \(a\) còn các con đường đi xa thành phố \(u\) sẽ có chi phí là \(b\). Con đường từ \(i\) tới \(j\) được gọi là hướng tới \(u\) nếu đường đi ngắn nhất từ \(i\) tới \(u\) dài hơn đường đi ngắn nhất \(j\) từ tới \(u\), ngược lại thì con đường từ \(i\) tới \(j\) được gọi là đi xa thành phố \(u\) . Khi sự kiện văn hóa diễn ra, một người di chuyển qua \(s\) con đường sẽ bị mất chi phí bằng tổng của từng lần di chuyển, lần di chuyển thứ \(k\) \((1 \leq k \leq s)\), sẽ mất chi phí \(k \cdot cost_{k}\) , trong đó \(cost_{k}\) bằng \(a\) hoặc \(b\) tùy thuộc lần di chuyển thứ đi qua con đường hướng tới thành phố tổ chức sự kiện
hay đi xa thành phố tổ chức sự kiện.

Một câu hỏi thường gặp ở đất nước \(Z\) là: nếu sự kiện văn hóa diễn tại thành phố \(u\), có hai người ở thành phố \(i\) và thành phố \(j\) thì chi phí nhỏ nhất để hai người gặp nhau tại một thành phố nào đó là bao nhiêu.

Yêu cầu: Cho thông tin về các con đường của đất nước \(Z\) và \(q\) câu hỏi, mỗi câu hỏi được mô tả bằng \(5\) số \(u, i, j, a, b\) cần trả lời chi phí nhỏ nhất để hai người gặp nhau.

Input

Dòng đầu tiên chứa hai số nguyên dương \(n\) và \(q\);

\(n - 1\) dòng sau, mỗi dòng chứa hai số nguyên \(x, y\) mô tả con đường nối giữa hai thành phố \(x, y\);

\(q\) dòng sau, mỗi dòng chứa năm số nguyên dương \(u, i, j, a, b\) mô tả một câu hỏi.

Output

Gồm \(q\) dòng, mỗi dòng là trả lời của câu hỏi trong
dữ liệu vào.

Example

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

6
80
20

Scoring

Có \(30\%\) số test tương ứng với \(30\%\) số điểm có : \(n, q \leq 1000\).

Có \(30\%\) số test tương ứng với \(30\%\) số điểm có : \(n \leq 2000\) và \(q \leq 10^5\).

Có \(20\%\) số test tương ứng với \(20\%\) số điểm có : \(n, q \leq 10^5\) và \(b \geq n \cdot a\).

Có \(20\%\) số test tương ứng với \(20\%\) số điểm có : \(n, q \leq 10^5\).

Sau bao năm vất vả học tập và giải những bài toán khó của Alice, Bob bây giờ đã là một quản lý của một công ty lớn. Một ngày đẹp trời nọ, Alice quyết định thăm Bob và cho Bob một bài toán khác để thử thách cậu.

Giả sử công ty của Bob gồm \(n\) nhân viên được đánh chỉ số từ \(1\) đến \(n\) và người thứ \(i\) có năng lực là \(a_i\). Một đội là một nhóm các nhân viên và năng lực của đội đó là tổng XOR (exclusive or) của năng lực của mọi người trong đội. Alice sẽ đưa ra tổng cộng \(q\) yêu cầu, mỗi yêu cầu thuộc một trong hai loại sau:

1. Thay đổi năng lực của nhân viên thứ \(i\) thành \(x\).
2. Đếm số cách chọn một đội mà mỗi nhân viên có chỉ số nằm trong đoạn \([l, r]\) và năng lực của đội đúng bằng \(s\).

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\) \((1 \leq n, q \leq 5 \times 10^{4})\) là số lượng nhân viên trong công ty của Bob và số lượng yêu cầu của Alice.

• Dòng tiếp theo chứa \(n\) số nguyên \(a_{1}, a_{2}, \ldots, a_n\) \((1 \leq a_{i} \leq 10^{6})\) là năng lực của các nhân viên.

• Trong \(q\) dòng tiếp theo, mỗi dòng chứa một số nguyên \(1\) hoặc \(2\). Số \(1\) theo sau bởi hai số nguyên \(i\) và \(x\) \((1 \leq i \leq n, 1 \leq x \leq 10^{6})\) mô tả yêu cầu loại \(1\). Số \(2\) theo sau bởi ba số nguyên \(l\), \(r\) và \(s\) \((1 \leq l \leq r \leq n\), \(1 \leq s \leq 10^{6})\) mô tả yêu cầu loại \(2\).

Output

• Đối với mỗi yêu cầu loại \(2\), in ra một số nguyên trên một dòng là phần dư của số cách chọn thỏa mãn khi chia cho \(10^{9} + 7\).

Example

3 3
1 2 3
2 1 3 3
2 1 2 3
2 1 3 1

2
1
2

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n, q \leq 20\).

• Subtask \(2\) (\(20\%\) số điểm): \(n \leq 10^{3}\), \(a_i \leq 10^{3}\), không có yêu cầu loại \(1\) và mọi yêu cầu loại \(2\) đều có \(l = 1\).

• Subtask \(3\) (\(30\%\) số điểm): \(n, q \leq 10^{3}\).

• Subtask \(4\) (\(30\%\) số điểm): Không có ràng buộc gì thêm.

Ở đất nước Byteland có \(N\) thành phố nhưng không có đường nào di chuyển giữa chúng. Tuy nhiên, mỗi ngày, một con đường mới sẽ được xây. Tổng cộng có \(m\) con đường.Trả lời \(q\) truy vấn: "Sau bao nhiêu ngày ta có thể di chuyển từ thành phố \(a\) sang \(b\)".

Input

• Dòng đầu tiên chứa ba số nguyên \(N\), \(M\) và \(Q\): số thành phố, con đường và truy vấn. Các thành phố được đánh số \(1, 2, \ldots, n\).

• \(M\) dòng sau thể hiện con đường được xây dựng. Mỗi dòng chứa hai số nguyên \(a\) và \(b\): có đường nối giữa \(a\) và \(b\)

• \(Q\) dòng cuối thể hiện mỗi truy vấn. Mỗi dòng gồm hai số nguyên \(a\) và \(b\): muốn di chuyển từ thành phố \(a\) sang \(b\).

Output

• Với mỗi truy vấn, in ra số ngày hoặc \(-1\) nếu không thể di chuyển.

Example

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

2
-1
4

Cho một cái cây có \(n\) nút và ta định nghĩa \(1\) là nút gốc của cây.

Bây giờ ta có \(q\) truy vấn, mỗi truy vấn có dạng: \(l_{i}\) \(r_{i}\) (\(1 \leq l_{i} \leq r_{i} \leq n\)).

Yêu cầu: Ứng với mỗi truy vấn, ta in ra LCA của tất cả các nút từ nút \(l_{i}\) đến nút \(r_{i}\)

Input

• Dòng thứ nhất chứa số n (\(2 \leq n \leq 300000\)) - Thể hiện số nút của cây

• \(n−1\) dòng tiếp theo, mỗi dòng gồm \(2\) số nguyên \(x,y\) - Thể hiện cạnh nối giữa hai đỉnh \(x\) và \(y\)

• Dòng tiếp theo, chứa số \(q\) (\(1 \leq q \leq 300000\)) - Thể hiện số lượng truy vấn

• \(q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(l_{i}\), \(r_{i}\) (\(1 \leq l_{i} \leq r_{i}\leq n\))

Output

• Ứng với mỗi truy vấn, in ra đáp án cần tìm.

Example

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

4
1

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(2 \leq n,q \leq 20\).

• Subtask \(2\) (\(60\%\) số điểm): Không có ràng buộc gì thêm.