Độ khó: Khó (4/4 điểm)

Lưu ý: Tuy đề bài yêu cầu dữ liệu với file nhưng trên web thì cứ mặc định là đọc từ bàn phím và in ra màn hình nha các bạn

Khách sạn X chuẩn bị bữa tiệc tối nay với một bàn tròn lớn gồm ~n~ ghế đánh số từ ~1~ đến ~n~ theo chiều kim đồng hồ: ghế thứ ~i~ ~(\forall i = 1, \dots, n-1)~ kề với ghế thứ ~i+1~ và ghế thứ ~n~ kề với ghế thứ ~1~.

Để đảm bảo tính thẩm mĩ, các ghế sẽ được phủ bằng khăn phủ ghế làm bằng vải thượng hạng, mỗi khăn phủ ghế được nhuộm một loại màu duy nhất. Khách sạn có tổng cộng ~k~ loại màu khăn được đánh số từ ~1~ đến ~k~, mỗi loại có số lượng vô hạn.

Trước giờ khai tiệc, đã có ~m~ ~(m \le n)~ chiếc ghế được phủ khăn, ghế thứ ~p_j~ ~(\forall j = 1, \dots, m)~ được phủ khăn màu ~c_j~. Các ghế còn lại chưa được phủ khăn và Quản lý có thể tự do chọn màu khăn phủ cho chúng sao cho thỏa mãn: "toàn bộ ~n~ ghế đều phải được phủ khăn và không có hai ghế kề nhau nào được phủ màu giống nhau".

Hãy đếm số cách mà Quản lý có thể chọn phủ khăn sao cho thỏa mãn điều kiện trên. Hai cách được coi là khác nhau nếu tồn tại một chiếc ghế được phủ màu khác nhau trong hai cách đó. Do số cách có thể rất lớn nên hãy in ra kết quả sau khi chia lấy dư cho ~10^9+7~.

Trong bài này, bạn cần trả lời ~T~ truy vấn như vậy.

Input

• Dòng đầu chứa số nguyên ~T~ ~(1 \le T \le 10^5)~ là số truy vấn cần trả lời;
• Tiếp theo là ~T~ truy vấn, truy vấn thứ ~i~ gồm:
  • Dòng đầu tiên chứa ba số nguyên ~n, k, m~ ~(3 \le n \le 10^{18}; 1 \le k \le 10^9; 0 \le m \le n)~;
  • Tiếp theo là ~m~ dòng, mỗi dòng chứa hai số nguyên ~p_j, c_j~ ~(1 \le p_j \le n; 1 \le c_j \le k)~.

Các ~p_j~ trong cùng một truy vấn đôi một khác nhau và được cho theo thứ tự bất kỳ.

Dữ liệu bảo đảm tổng của các ~m~ trên toàn bộ ~T~ truy vấn không vượt quá ~2 \cdot 10^5~.

Output

Gồm ~T~ dòng, dòng thứ ~i~ ~(1 \le i \le T)~ là câu trả lời cho truy vấn thứ ~i~ (chia lấy dư cho ~10^9+7~).

Scoring

Sample Input 1

3
5 3 0
6 3 2
1 1
4 2
4 2 1
1 1

Sample Output 1

30
9
1

Notes

Truy vấn ~1~: tổng cộng ~30~ cách phủ khăn thỏa mãn.

Truy vấn ~2~: tổng cộng ~9~ cách phủ khăn thỏa mãn.

Truy vấn ~3~: chỉ có hai cách phủ khăn để không có hai ghế liền kề cùng màu. Trong đó chỉ có một cách mà ghế ~1~ được phủ khăn màu ~1~.

Độ khó: Khó (4/4 điểm)

Lưu ý: Tuy đề bài yêu cầu dữ liệu với file nhưng trên web thì cứ mặc định là đọc từ bàn phím và in ra màn hình nha các bạn

Một nông trại có ~n~ khu vườn nối với nhau bởi ~n-1~ con đường, mỗi con đường nối giữa hai khu vườn với nhau tạo thành dạng một cây đồ thị. Khi thu hoạch người ta chọn khu vườn ~1~ làm gốc của cây đồ thị. Khu vườn ~i~ đang có ~a_i~ thùng hoa quả. Ta quy ước "nhánh của khu ~u~" bao gồm khu vườn ~u~ và mọi khu vườn nằm trong cây con nhận ~u~ làm gốc.

Trong ngày, diễn ra ~q~ sự kiện thuộc hai loại:

• ~1~ ~u~ ~x~: Toàn bộ các khu vườn thuộc nhánh khu ~u~, mỗi khu thu hoạch thêm ~x~ thùng hoa quả;
• ~2~ ~u~: Tính tổng số thùng hoa quả có trong toàn bộ các khu vườn thuộc nhánh của khu ~u~.

Hãy in ra câu trả lời cho các sự kiện loại ~2~ theo đúng thứ tự dữ liệu đầu vào.

Input

• Dòng ~1~ chứa hai số nguyên ~n, q~ ~(1 \le n, q \le 2 \cdot 10^5)~ lần lượt là số khu vườn và số sự kiện diễn ra trong ngày;
• Dòng ~2~ chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ ~(0 \le a_i \le 10^9, 1 \le i \le n)~;
• Tiếp theo là ~n-1~ dòng, mỗi dòng chứa hai số nguyên ~u, v~ mô tả một con đường ~(1 \le u, v \le n; u \ne v)~. Các con đường được cho theo thứ tự bất kì và không bảo đảm ~u~ là cha của ~v~. Dữ liệu bảo đảm ~n-1~ con đường này tạo thành một cây đồ thị;
• Cuối cùng là ~q~ dòng, mỗi dòng mô tả một sự kiện thuộc một trong hai loại theo mô tả đề bài ~(1 \le u \le n; 1 \le x \le 10^4)~.

Output

Gồm nhiều dòng, mỗi dòng là một số nguyên tương ứng với câu trả lời cho sự kiện loại ~2~ theo thứ tự dữ liệu đầu vào.

Scoring

Sample Input 1

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

Sample Output 1

11
41
45
14

Notes

Nhánh của khu ~2~ gồm ~\{2,4,5\}~ với tổng số thùng là ~2+4+5=11~ thùng.

Sự kiện ~1~ tiếp theo cộng ~10~ thùng cho cả ba khu này nên tổng số thùng của nhánh trở thành ~12+14+15=41~ thùng.

Toàn nông trại khi đó có ~45~ thùng và riêng khu ~4~ có ~14~ thùng.

Độ khó: Khó (4/4 điểm)

Lưu ý: Tuy đề bài yêu cầu dữ liệu với file nhưng trên web thì cứ mặc định là đọc từ bàn phím và in ra màn hình nha các bạn

Bạn đang chơi trò chơi "Chiến dịch tập kích" với bản đồ gồm ~N~ thành phố (đánh số từ ~1~ đến ~N~) được nối bởi ~M~ con đường một chiều. Để đi hết con đường thứ ~i~ cần tốn ~w_i~ đơn vị thời gian. Bạn xuất phát vào thời điểm ~0~ tại thành phố ~1~ và cần phá hủy mục tiêu được đặt ở thành phố ~N~.

Có một số thành phố được bảo vệ bởi lá chắn phòng thủ. Lá chắn phòng thủ của một thành phố được duy trì bởi một số trạm phát đặt tại những thành phố khác. Muốn tiến vào một thành phố có lá chắn phòng thủ, trước hết phải phá hủy toàn bộ các trạm phát duy trì lá chắn đó; mà muốn phá một trạm phát thì phải tiến được vào thành phố chứa trạm phát ấy.

Bạn có vô số robot cảm tử. Mỗi khi tiến vào một thành phố, một robot lập tức phá hủy một mục tiêu tại đó (phá hủy một trạm phát hoặc mục tiêu ở thành phố ~N~). Việc phá hủy không tốn thời gian; chỉ việc di chuyển trên các con đường mới tốn thời gian.

Hãy tính thời gian ít nhất để phá hủy được mục tiêu ở thành phố ~N~.

Input

• Dòng đầu gồm hai số nguyên ~N~ và ~M~ ~(1 \le N \le 10^5, 1 \le M \le 3 \cdot 10^5)~;
• ~M~ dòng tiếp theo, mỗi dòng gồm ba số nguyên ~u_i, v_i, w_i~ ~(1 \le w_i \le 10^8)~ mô tả một con đường một chiều đi từ thành phố ~u_i~ tới thành phố ~v_i~ tốn ~w_i~ đơn vị thời gian;
• ~N~ dòng tiếp theo, dòng thứ ~v~ mô tả thành phố ~v~: bắt đầu bằng số nguyên ~l_v~ là số trạm phát duy trì lá chắn của thành phố ~v~, tiếp theo là ~l_v~ số hiệu thành phố cho biết vị trí đặt mỗi trạm phát. Nếu ~l_v = 0~ thì thành phố ~v~ không có lá chắn (thành phố ~1~ bảo đảm không có lá chắn, tức ~l_1 = 0~).

Dữ liệu bảo đảm luôn có phương án phá hủy mục tiêu và không có trạm phát duy trì lá chắn của một thành phố nào lại nằm trong chính thành phố đó. Có thể có nhiều con đường nối cùng một cặp thành phố và có thể có đường đi từ một thành phố tới chính nó.

Output

Một số nguyên duy nhất là thời gian ít nhất để phá hủy được mục tiêu ở thành phố ~N~.

Scoring

Sample Input 1

6 6
1 2 1
1 4 3
2 3 1
2 5 2
4 6 2
5 3 2
0
0
0
1 5
0
2 3 5

Sample Output 1

5

Notes

Thành phố ~4~ có lá chắn do trạm phát ở thành phố ~5~ duy trì.

Thành phố ~6~ có lá chắn do hai trạm phát ở thành phố ~3~ và ~5~ duy trì.

Phương án tối ưu tiến vào các thành phố theo thứ tự lần lượt là: ~2 \rightarrow 3 \rightarrow 5 \rightarrow 4 \rightarrow 6~.

Đáp án là ~5~.