양갈래 바이러스

여행을 다니던 무대소녀 나나는 어느 날 갈래 나라를 발견한다. 갈래 나라는 $N$개의 도시로 이루어져 있고, $i$ ($2 \leq i \leq N$)번째 도시와 $\left \lfloor \frac{i}{2} \right \rfloor$번째 도시를 잇는 양방향 도로가 있다. $N = 2^k - 1$을 만족하는 양의 정수 $k$가 존재한다. 즉, 갈래 나라는 포화 이진 트리 구조를 이룬다.

갈래 나라 국민 중에는 양갈래 머리를 한 사람이 한 명도 없었다. 충격을 받은 나나는 무대소녀로서의 일을 잠시 접고 $Q$종류의 양갈래 바이러스를 만든다.

각 바이러스에는 위력 $p$와 전염력 $d$가 있다. 도시 $v$에 뿌려진 바이러스는 $v$에서 거리가 $d$ 이하인 도시를 감염시키며, 감염된 도시는 위력 $p$만큼 감염도가 오른다. 도시 $a$에서 도시 $b$까지의 거리는 $a$에서 $b$로 가는 경로에서 거쳐야 하는 도로 개수의 최솟값이다.

도시의 감염도는 나나가 모든 바이러스를 뿌린 후, 그 도시를 감염시킨 바이러스 위력의 합이다. 한 도시는 두 종류 이상의 바이러스에 감염될 수 있다.

모든 바이러스를 뿌린 뒤 각 도시의 감염도를 출력하라.

첫째 줄에 도시의 개수 $N$ ($1\leq N < 262\,144 = 2^{18}$)과 바이러스의 개수 $Q$ ($1 \leq Q \leq 200\,000$)가 공백으로 구분되어 주어진다.

둘째 줄부터 $Q$개의 줄에는 바이러스 정보가 $v$ $p$ $d$ 형식으로 주어진다. 이는 $v$ ($1 \leq v \leq N$)번째 도시에 위력 $p$ ($1 \leq p \leq 1\,000$), 전염력 $d$ ($0 \leq d \leq (\log_2 (N + 1) - 1) \times 2$)인 바이러스를 뿌린다는 뜻이다.

각 도시의 감염도를 번호 순서대로 공백으로 구분하여 $N$개의 수로 출력하라.