Bài tập

Một khu rừng cổ xưa được quản lý bởi các nhà pháp sư. Khu rừng này bao gồm \(n\) cây, mỗi cây được xem là một đỉnh trong một cây thần linh khổng lồ. Ban đầu, mỗi đỉnh đều có năng lượng bằng \(0\). Nhiệm vụ của các pháp sư là sử dụng phép thuật để tăng cường sức mạnh cho các đỉnh và kiểm tra sự phân phối năng lượng trên các con đường trong cây.

Mỗi ngày, các pháp sư sẽ thực hiện một trong hai loại phép thuật sau:

• Loại 1: Gọi \(d(i)\) là đỉnh thứ \(i\) khi đi trên đường đi ngắn nhất từ \(u\) đến \(v\). Họ sẽ truyền thêm năng lượng cho các đỉnh trên đường đi, theo quy tắc \(a(d(i)) += i \times x\).
• Loại 2: Họ kiểm tra tổng năng lượng của tất cả các đỉnh trên con đường ngắn nhất giữa hai đỉnh \(u\) và \(v\).

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\) \((1 \leq n, q \leq 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:

• 1 u v x: Thực hiện phép thuật loại 1.

• 2 u v: Thực hiện phép thuật loại 2.

Ràng buộc: \(1 \le u, v \le n\) , \(1 \le x \le 10^6\).

Output

• Với mỗi truy vấn loại \(2\), in ra một số nguyên duy nhất thể hiện tổng năng lượng \(mod\) \((10^9 + 7)\).

Example

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

10
18

Scoring

• Subtask 1 (30% số điểm): \(n, q \leq 1000\).
• Subtask 2 (30% số điểm): Cây có dạng đường thẳng.
• Subtask 3 (40% số điểm): Không có ràng buộc thêm.

Không khí Tết đang rộn ràng khắp mọi nơi. Để chào đón năm mới, các thành viên câu lạc bộ CHTCoder quyết định treo một dãy lồng đèn dọc theo hành lang chính của trường. Hành lang có độ dài \(L\). Ban đầu, các bạn dự định treo \(N\) chiếc đèn lồng tại các vị trí \(a_1, a_2, \dots, a_N\) \((0 < a_1 < a_2 < \dots < a_N < L)\). Hai đầu hành lang (vị trí \(0\) và \(L\)) được xem là hai cột mốc cố định (trên cột mốc đã có đèn lồng).

Tuy nhiên, sau khi treo thử, mọi người nhận thấy mật độ đèn quá dày dẫn đến nhìn rối mắt. Vì vậy, CLB quyết định sẽ tháo bớt tối đa \(M\) chiếc đèn lồng trong số các vị trí dự kiến ban đầu (không thay đổi hai đầu mốc \(0\) và \(L\)).

Yêu cầu: Hãy giúp CHTCoder chọn cách tháo bớt đèn sao cho khoảng cách nhỏ nhất giữa hai chiếc đèn lồng bất kỳ còn lại là lớn nhất có thể, giúp hành lang trở nên thoáng đãng và lung linh nhất.

Input

Vào từ tệp văn bản LANTERN.INP theo cấu trúc:

• Dòng đầu tiên ghi ba số nguyên dương \(L, N, M\) \((1 \le L \le 10^9; 0 \le M \le N \le 10^6)\)
• Dòng thứ hai ghi \(N\) số nguyên \(a_1, a_2, \dots, a_N\) là tọa độ các vị trí dự kiến treo đèn.

Output

Ghi ra tệp văn bản LANTERN.OUT một số nguyên duy nhất là kết quả tìm được.

Example

25 5 2
2 11 14 17 21

4

Scoring

• Có \(40\%\) số test ứng với \(40\%\) số điểm của bài với \(N \le 20\);
• Có \(40\%\) số test ứng với \(40\%\) số điểm của bài với \(M = 0\) và \(N \le 10^6\);
• Có \(20\%\) số test ứng với \(20\%\) số điểm của bài với \(N \le 10^5\);

Trong một thiên hà xa xôi, một nền văn minh cổ đại đã phát triển một hệ thống số học phức tạp để đo lường năng lượng của các vì sao. Năng lượng của một chòm sao, được biểu diễn bằng một số nguyên không âm \(a\), khi được kích hoạt bởi một hằng số vũ trụ \(b\), sẽ tạo ra một giá trị năng lượng mới. Giá trị này được tính toán bằng phép toán luỹ thừa, nhưng để tránh sự quá tải năng lượng, kết quả phải được lấy theo một modulo đặc biệt, là \(10^9 + 7\).

Tuy nhiên, có một trường hợp đặc biệt mà các nhà thiên văn học cổ đại đã ghi chép lại: khi một chòm sao có năng lượng ban đầu là 0 được kích hoạt bởi hằng số 0, nó sẽ tạo ra một năng lượng kích hoạt cơ bản bằng 1.

Bạn là một nhà toán học vũ trụ, được giao nhiệm vụ giải mã những công thức cổ đại này. Bạn cần xây dựng một chương trình để tính toán giá trị năng lượng cuối cùng cho một loạt các chòm sao và hằng số vũ trụ được đưa ra.

Yêu cầu: Cho các cặp số nguyên không âm \((a, b)\), hãy tính giá trị \(a^b \pmod{10^9 + 7}\). Lưu ý rằng theo quy tắc đặc biệt, \(0^0 = 1\).

Input

• Dòng đầu tiên chứa một số nguyên \(n\) (\(1 \le n \le 2 \cdot 10^5\)), là số lượng câu hỏi.
• \(n\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(a, b\) (\(0 \le a, b \le 10^9\)).

Output

• In ra \(n\) dòng, mỗi dòng chứa một số nguyên là kết quả của phép tính \(a^b \pmod{10^9 + 7}\) tương ứng với mỗi cặp \((a, b)\) trong dữ liệu vào.

Example

3
3 4
2 8
123 123

81
256
921450052

Scoring

• Subtask \(1\) (\(50\%\) số điểm) : \(n, a, b \leq 1000\).
• Subtask \(2\) (\(50\%\) số điểm) : không có ràng buộc gì thêm.

Bạn đang khám phá một tòa nhà lớn gồm \(R\) hàng và \(C\) cột phòng, tạo thành một lưới ô vuông kích thước \(R \times C\). Ô ở góc trái trên là ô \((1,1)\) và ô ở góc phải dưới là \((R,C)\).

Mỗi căn phòng của tòa nhà này có một mức độ bảo vệ \(A_{i,j}\) và trong mỗi phòng có chứa một gói kẹo loại \(B_{i,j}\). Bạn sẽ bắt đầu tại một căn phòng \((x, y)\) và chỉ được phép đi qua các phòng có mức độ bảo vệ không vượt quá \(k\) thì số loại kẹo khác nhau lớn nhất bạn thu thập được là bao nhiêu.

Lưu ý rằng bạn chỉ có thể di chuyển sang các phòng kề nhau theo bốn hướng: trái, phải, trên, dưới.

Không dừng lại ở đó, tòa nhà này lại thay đổi theo thời gian, nghĩa là sẽ có thời điểm loại kẹo tại một phòng bị thay đổi. Xen giữa những lần thay đổi này, bạn được yêu cầu trả lời các câu hỏi có dạng \((x,y,a)\) như trên.

Bạn cần xử lý \(Q\) truy vấn sau:

• 1 \(x\) \(y\) \(b\) --- loại kẹo tại hàng \(x\), cột \(y\) được thay đổi thành \(b\).
• 2 \(x\) \(y\) \(a\) --- nếu bắt đầu từ phòng \((x, y)\), chỉ được đi qua các phòng có độ khó \(\le a\), hãy tính xem bạn có thể thu thập được bao nhiêu loại kẹo khác nhau trong vùng bạn đi đến.

Ràng buộc: mức độ bảo vệ của các phòng đôi một khác nhau.

\InputFile

• Dòng đầu tiên chứa ba số nguyên \(R\), \(C\), \(Q\) (\(1 \le R \times C \le 10000\))
• \(R\) dòng tiếp theo: mỗi dòng gồm \(C\) số nguyên \(A_{i,j}\) (\(1 \le A_{i,j} \le 10^9\))
• \(R\) dòng tiếp theo: mỗi dòng gồm \(C\) số nguyên \(B_{i,j}\) (\(1 \le B_{i,j} \le 10000\))

• \(Q\) dòng tiếp theo, mỗi dòng ghi lần lượt một trong hai truy vấn sau:

• 1 \(x\) \(y\) \(b\): \(1 \le x \le R, \; 1 \le y \le C, \; 1 \le b \le 10000;\)

• 2 \(x\) \(y\) \(a\): \(1 \le x \le R, \; 1 \le y \le C, \; 1 \le a \le 10^9;\)

\OutputFile

Với mỗi truy vấn loại 2, in ra một dòng --- số lượng loại phòng khác nhau bạn có thể tiếp cận được.

\Scoring

• Subtask 1 (\(10\%\) số điểm): \(R = 1\), \(1 \le Q \le 1000\), \(A_{1,j} = j\) và không có truy vấn loại 1.
• Subtask 2 (\(20\%\) số điểm): \(1 \le Q \le 100\)
• Subtask 3 (\(24\%\) số điểm): Không có truy vấn loại \(1\).
• Subtask 4 (\(20\%\) số điểm): \(R = 1\), \(1 \le Q \le 10^5\)
• Subtask 5 (\(26\%\) số điểm): Không giới hạn gì thêm

Example

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

4
3
0