Nam có một cái cây rất đẹp. Cây của Nam gồm ~S~ nút (tính cả gốc) và ~S - 1~ cành cây nối giữa các nút. Gốc cây được đánh số 1. Trừ gốc cây, mỗi nút đều có một "cha" là nút tiếp theo trên đường đi từ nó đến gốc. Nút ~u~ được gọi là tổ tiên của nút ~v~ nếu ~u~ nằm trên đường đi từ ~v~ đến gốc. Gốc cây là tổ tiên của tất cả các nút còn lại.

Mỗi nút trên cây có một độ tươi tốt khác nhau. Lúc đầu, tất cả các nút đều có độ tươi tốt là 0. Nam chăm sóc cái cây của mình hàng ngày trong ~D~ ngày liên tiếp. Ở ngày thứ ~i~, Nam chọn một trong hai thao tác sau:

• 1 ~u, k~: tưới nước cho ~u~ và tất cả các tổ tiên của nó. Độ tươi tốt của các nút này sẽ tăng thêm ~k~.
• 2 ~u, k~: bón phân cho ~u~ và các nút ~v~ sao cho ~u~ là tổ tiên của ~v~. Độ tươi tốt của các nút này sẽ tăng thêm ~k~.

Sau ~D~ ngày, Nam muốn tổng kết lại độ tươi tốt của các nút trên cây. Tuy nhiên, các cây lúc này đã quá tươi tốt để Nam có thể đo độ tươi tốt. Rất may là Nam đã tỉ mỉ ghi chép lại nhật kí tưới cây của mỗi ngày trong số ~D~ ngày đã qua. Bạn hãy giúp Nam tính độ tươi tốt của mỗi nút sau ~D~ ngày nhé!

Yêu cầu: Tính độ tươi tốt của mỗi nút sau ~D~ ngày.

Input

• Dòng đầu tiên gồm hai số ~S~ và ~D~ (~S, D \le 500000~).
• Dòng thứ hai gồm ~S - 1~ số ~p_2, p_3, \dots, p_S~ (~1 \le p_i < i~), thể hiện nút ~p_i~ là cha của nút ~i~.
• ~D~ dòng sau, dòng thứ ~i~ gồm ba số ~t, u, k~ (~1 \le t \le 2, 1 \le u \le S, 1 \le k \le 10^9~), thể hiện việc chăm sóc cây của Nam trong ngày ~i~.

Output

• Dòng duy nhất ghi ~S~ số, số thứ ~i~ thể hiện độ tươi tốt của nút thứ ~i~ sau ~D~ ngày.

Sample Input 1

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

Sample Output 1

6 1 2 3