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.

Cho một dãy \(n\) số nguyên dương \(a_0, a_1, \ldots, a_{n-1}\).

Với mọi \(U\) thỏa mãn \(0 \leq U < n\): Tính tổng \(a_i \cdot a_j\) với mọi \(0\leq i,j < n, (i\text{ or }j) \leq U\).

Toán tử or ở đây biểu thị cho toán tử nhị phân OR.

Input

• Dòng đầu chứa số nguyên duy nhất là \(n\) \((1 \leq n \leq 2 \cdot 10^5)\), độ dài mảng \(a\).

• Dòng thứ hai chứa \(n\) số nguyên dương \(a_0, a_1, \ldots, a_{n-1}\) \((0 < a_{i} \leq 10^7)\).

Output

• In ra \(n\) số nguyên dương trên cùng một dòng duy nhất. Số thứ \(i\) là đáp án cho \(U = i - 1\) khi chia dư cho \(10^9 + 7\).

Example

3
1 2 8

1 9 89 

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \le 500\).

• Subtask \(2\) (\(30\%\) số điểm): \(n \le 10^4\).

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

Cho dãy \(A\) gồm \(N\) số nguyên dương \(a_{1}, a_{2}, … ,a_{N}\) và một số nguyên dương \(K\) . Một đoạn con của \(A\) là một dãy liên tục các phần tử của \(A\). Một đoạn con của \(A\) được gọi là hài hòa nếu trung bình cộng của các phần tử trong đoạn con đó đúng bằng \(K\).

Yêu cầu: Hãy tìm đoạn con hài hòa dài nhất bằng cách chỉ ra độ dài và chỉ số phần tử đầu tiên của đoạn con đó. Nếu tồn tại nhiều đoạn con như vậy thì đưa ra đoạn con có chỉ số của phần tử đầu tiên nhỏ nhất. Nếu không tồn tại đoạn con nào thỏa mãn thì ghi ra số \(0\).

Input

Đọc từ tệp văn bản BAI4.INP có cấu trúc:

--- Dòng đầu tiên ghi hai số nguyên dương \(N\) và \(K\) \((1 ≤ N ≤ 10^5), 1 ≤ K ≤ 10^9)\);

--- Dòng thứ hai chứa \(N\) số nguyên \(a_{1}, a_{2}, … ,a_{N}\) \((1 ≤ a_{i} ≤ 10^9, i = 1, 2, … , N)\);

--- Các số cách nhau một dấu cách.

Output

Ghi ra tệp văn bản BAI4.OUT hai số nguyên dương là độ dài và chỉ số phần tử đầu tiên của đoạn con tìm được, các số ghi trên một dòng và cách nhau một dấu cách hoặc ghi ra số \(0\) nếu không tồn tại đoạn con nào thỏa mãn điều kiện của bài toán.

Example

5 3
1 2 3 4 6

3 2

4 3
1 2 5 6

0

Scoring

--- Có \(30\%\) số test tương ứng với \(30\%\) số điểm có \(N ≤ 100\).

--- Có \(60\%\) số test tương ứng với \(60\%\) số điểm có \(N ≤ 5000\).

--- \(10\%\) còn lại không có ràng buộc gì thêm.

--- Thời gian thực hiện mỗi test không quá một giây.