Alice đang phải tạo dữ liệu là một đồ thị dạng cây. Cô đã tạo được một cây gồm ~n~ đỉnh, các đỉnh được đánh số hiệu từ ~1~ đến ~n~. Cạnh thứ ~k~ ~(1 \leq k \leq n - 1)~ nối hai đỉnh phân biệt có số hiệu ~u_k, v_k \ (1 \leq u_k, v_k \leq n)~. ALice muốn tạo ra các cây mới bằng cách xóa đi ít nhất một đỉnh và xóa tất cả các cạnh kề với đỉnh được xóa mà phần còn lại (có ít nhất một đỉnh) vẫn liên thông với nhau. Một cách xóa được gọi là đẹp nếu tập số hiệu của các đỉnh còn lại là một tập gồm các số hiệu liên tiếp nhau.

Yêu cầu:

Cho dãy ~(u_1, v_1), \ (u_2, v_2), \dots, \ (u_{n - 1}, v_{n - 1})~ mô tả cây, hãy đếm số cách xóa đẹp. Hai cách xóa được gọi là khác nhau nếu tồn tại một đỉnh trong cách này bị xóa mà cách kia không bị xóa.

Dữ liệu

• Dòng đầu chứa số nguyên dương ~n \ (1 \leq n \leq 3 \times 10^5)~.
• Dòng thứ ~k \ (1 \leq k \leq n - 1)~ chứa hai số nguyên dương ~u_k, v_k \ (1 \leq u_k, v_k \leq n)~.

Kết quả

• Ghi ra thiết bị ra chuẩn một dòng chứa một số là số cách xóa đẹp.

Ràng buộc

• Subtask ~1 \ (10 \%)~: ~n \leq 100~ và đồ thị có dạng đường thẳng.
• Subtask ~2 \ (20 \%)~: ~n \leq 5000~ và đồ thị có dạng đường thẳng.
• Subtask ~3 \ (20 \%)~: Đồ thị có dạng đường thẳng.
• Subtask ~4 \ (20 \%)~: ~n \leq 100~.
• Subtask ~5 \ (10 \%)~: ~n \leq 5000~.
• Subtask ~6 \ (10 \%)~: Không có ràng buộc gì thêm.

Sample Input 1

4
1 2
3 2
4 2

Sample Output 1

8

Sample Input 2

5
1 5
5 3
3 4
4 2

Sample Output 2

9

Bạn đang leo dốc trong một thành phố trên núi.

Nơi thành phố bạn sống đặc biệt có những con đường cao tít tựa Đà Lạt. ~N~ căn nhà nơi đây có thể đến được với nhau bằng ~M~ con đường hai chiều, con đường thứ ~i~ có độ dài ~w_i~ và độ cao là ~c_i~. Căn nhà cuối cùng (thứ ~N~) trên đỉnh núi là nơi bạn cần đến, từ căn nhà số ~1~ bạn cần đến đó nhanh nhất có thể nhưng điều đó không thành vấn đề vì bạn đã quá rành đường nơi đây rồi.

Điều bạn cần là tìm con đường có thể tối đa hoá độ cao giữa đường cao nhất và đường thấp nhất mà vẫn đảm bảo về thời gian, bởi leo trèo là việc bạn thích nhất. Liệu bạn có biết chênh lệch tối đa đó không?

Input

• Dòng đầu tiên gồm hai số nguyên dương là ~N~ và ~M~ (~1 \leq N \leq 2 \cdot 10^5, 1 \le M \leq 3 \cdot 10^5~).

• ~M~ dòng tiếp theo dòng thứ ~i~ gồm bốn số ~u_i~, ~v_i~, ~w_i~, ~c_i~ (~1 \leq u_i \neq v_i \leq N~, ~1 \leq w_i, c_i \leq 10^9~) lần lượt cho biết độ dài và độ cao của con đường nối hai địa điểm ~u_i~ và ~v_i~. Giữa hai địa điểm không có quá một con đường.

Đề đảm bảo luộn tồn tại đường đi từ ~1~ đến ~N~.

Output

Ghi ra một số duy nhất cho biết chênh lệch lớn nhất bạn cần mà vẫn đảm bảo thời gian di chuyển là ngắn nhất.

Scoring

Sample Input 1

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

Sample Output 1

6

Quân đội của đại tướng Trần có ~n~ đơn vị được đánh số từ ~1~ đến ~n~. Đơn vị ~1~ có cấp bậc cao nhất, còn các đơn vị ~i~ với ~2 \le i \le n~ sẽ nhận đơn vị ~p_i~ làm cấp trên trực tiếp. Đảm bảo rằng, cách sắp xếp cấp bậc này được dựa trên mô hình cây. Nói cách khác, mô hình quân đội là một cây có gốc ở đỉnh ~1~. Ngoài ra, đơn vị thứ ~i~ có quân số là ~a_i~.

Một cách triệu tập quân đội với đơn vị ~u~ là chỉ huy là việc chọn một dãy các đơn vị ~x_1, x_2, \dots, x_k~, mỗi đơn vị lấy duy nhất một binh sĩ, sao cho ~x_1 = u~ và ~p_{x_{i+1}} = x_i~ với ~1 \le i \le k - 1~.

Gọi ~S(u)~ là số cách triệu tập quân đội với ~u~ là chỉ huy.

Để kiểm tra sự linh hoạt của hệ thống quân đội, đại tướng Trần cần bạn thiết kế một chương trình thực hiện một dãy các thao tác sau:

• Thay đổi quân số của một đơn vị bất kỳ.

• Chọn một đơn vị ~u~ bất kỳ, tính ~S(u)~.

Yêu cầu: Hãy thực hiện các yêu cầu trên của đại tướng để nhận được phần thưởng hậu hĩnh.

Input

• Dòng đầu tiên gồm hai số nguyên ~n~ và ~q~ (~1 \le n, q \le 2 \cdot 10^5~) — số đơn vị và số yêu cầu của đại tướng Trần.

• Dòng thứ hai gồm ~n - 1~ số nguyên dương ~p_2, p_3, \dots, p_n~ (~p_i \lt i~) — cấp trên trực tiếp của đơn vị ~i~.

• Dòng thứ ba gồm ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~ (~1 \le a_i \le 10^9~) — quân số của đơn vị ~i~.

• ~q~ dòng cuối cùng, mỗi dòng là một truy vấn thuộc một trong hai dạng:

  • ~1~ ~u~ ~x~ (~1 \le u \le n, 1 \le x \le 10^9~): Gán ~a_u = x~.

  • ~2~ ~u~ (~1 \le u \le n~): Tính ~S(u)~.

Output

• Với mỗi truy vấn loại ~2~, in ra một số nguyên trên một dòng là kết quả của truy vấn, lấy dư cho ~10^9 + 7~.

Sample Input 1

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

Sample Output 1

5
10

Notes

• Ta có dãy ban đầu ~a = [1,1,2,2]~. Định nghĩa ~x_y~ là binh sĩ thứ ~y~ ở đơn vị ~x~.

• Khi ~a_2 = 1~ thì ~S(2) = 5~, gồm các cách chọn sau: ~[2_1]~, ~[2_1,3_1]~, ~[2_1,3_2]~, ~[2_1,4_1]~, ~[2_1,4_2]~.

• Sau khi cập nhật ~a_2 = 2~, ta có thêm ~5~ cách chọn nữa, mỗi cách đều chọn binh sĩ ~2_2~.

Sau khi thua hết tiền tại bàn Poker, Hùng vẫn quả quyết rằng mình rất đẳng cấp và nhài cá đã can thiệp vào kết quả trò chơi. Để tìm hiểu thêm về lí do thua trận, Hùng lần này quyết định thử làm Dealer. Một việc vô cùng quan trọng của một Dealer là tráo bài: và Hùng quyết định thử gian lận ở phần này. Bộ bài của Hùng có ~n~ lá, và Hùng sẽ chia đúng ~n~ lá này cho người chơi. Thay vì xáo trộn như bình thường, trong lần chia bài thứ ~i~, Hùng sẽ:

• Lấy lá bài trên cùng cho về cuối bộ bài. Hùng sẽ lặp lại thao tác này ~a_i~ lần (hoặc thậm chí không thèm tráo bài khi ~a_i = 0~).
• Lấy ra lá bài trên cùng và đưa cho người chơi.

Ở vị trí người chơi, Tèo đang ngồi nhìn Hùng tráo bài một cách vô cùng bẩn mắt. Vốn hiểu rất rõ người bạn của mình, tất nhiên là Tèo biết được dãy số ~a_i~ của Hùng và đồng thời Tèo cũng biết rằng bộ bài ban đầu chưa hề được tráo: tức lá thứ nhất mang số ~1~, lá thứ hai mang số ~2~, ... và lá thứ ~n~ mang số ~n~.

Từ dãy ~a~ mà Tèo biết và dữ kiện ban đầu, bạn hãy giúp Tèo xem cậu sẽ lần lượt nhận được các lá bài mang giá trị bao nhiêu?

Input

• Dòng đầu chứa số nguyên dương ~n~ ~(1 \le n \le 5 \times 10^5)~.
• Dòng sau chứa ~n~ số nguyên ~a_1, a_2, \ldots, a_n)~ ~(0 \le a_i \lt n)~.

Output

• In ra ~n~ số, số thứ ~i~ là giá trị trên lá bài mà Tèo nhận được ở lần thứ ~i~.

Scoring

• Subtask 1 ~(20\%)~: ~N \le 200~.
• Subtask 2 ~(30\%)~: ~N \le 5000~.
• Subtask 2 ~(50\%)~: Không có giới hạn gì thêm.

Sample Input

5
2 1 2 2 0

Sample Output

3 5 4 1 2

Giải thích:

• Ban đầu bộ bài có các giá trị là ~[1, 2, 3, 4, 5]~.
• Ở lượt thứ nhất, ~a_i = 2~, bộ bài trở thành ~[3, 4, 5, 1, 2]~. Tèo nhận được lá ~3~ và bộ bài còn ~[4, 5, 1, 2]~.
• Ở lượt thứ hai, ~a_i = 1~, bộ bài trở thành ~[5, 1, 2, 4]~. Tèo nhận được lá ~5~ và bộ bài còn ~[1, 2, 4]~.
• Ở lượt thứ ba, ~a_i = 2~, bộ bài trở thành ~[4, 1, 2]~. Tèo nhận được lá ~4~ và bộ bài còn ~[1, 2]~.
• Ở lượt thứ tư, ~a_i = 2~, bộ bài trở thành ~[1, 2]~. Tèo nhận được lá ~1~ và bộ bài còn ~[2]~.
• Ở lượt thứ năm, ~a_i = 0~, bộ bài còn một lá ~2~ và Tèo nhận được lá này.

Cho một bộ nhớ đệm có kích thước ~n~, trong đó máy của bạn sẽ chỉ đọc được giá trị trong các ô nhớ từ ~1~ đến ~k~ ~(k \le n)~. Hiện tại, trong bộ nhớ đệm đang chứa một hoán vị có độ dài ~n~, với vị trí thứ ~i~ đang lưu số ~a_i~.

Hùng muốn đọc các số từ ~1~ đến ~n~ từ trong bộ nhớ, lần lượt theo thứ tự tăng dần. Để đọc được giá trị tại các vị trí mà ban đầu chưa đọc được, Hùng có thể thực hiện một trong hai thao tác như sau:

1. Chuyển tất cả các giá trị của từng ô sang ô liền kề bên trái, giá trị ở ô thứ ~1~ sẽ chuyển sang ô thứ ~n~.
2. Chuyển tất cả các giá trị của từng ô sang ô liền kề bên phải, giá trị ở ô thứ ~n~ sẽ chuyển sang ô thứ ~1~.

Nhiệm vụ của bạn là hãy tìm số thao tác chuyển giá trị tối thiểu Hùng cần sử dụng để đạt được mục đích.

Input

• Dòng đầu chứa hai số nguyên dương ~n~ và ~k~ ~(1 \le k \le n \le 10^6)~.
• Dòng sau chứa ~n~ số ~a_1, a_2, \ldots a_n~ là các giá trị ban đầu của bộ nhớ đệm. Dãy ~a~ là một hoán vị độ dài ~n~.

Output

• In ra một số nguyên duy nhất là số thao tác tối thiểu Hùng cần sử dụng.

Scoring

• Subtask 1 ~(30\%)~: ~n \le 200~.
• Subtask 2 ~(30\%)~: ~n \le 2000~
• Subtask 3 ~(40\%)~: Không có giới hạn gì thêm.

Sample Input

5 3
2 5 1 4 3

Sample Output

3

Giải thích:

• Ban đầu ~a = [2, 5, 1, 4, 3]~, Hùng đọc được giá trị ~1, 2~.
• Hùng dùng hai thao tác loại 2 để ~a = [4, 3, 2, 5, 1]~, sau đó đọc giá trị ~3, 4~.
• Hùng dùng một thao tác loại 1 để ~a = [3, 2, 5, 1, 4]~, sau đó đọc giá trị ~5~.