31480번 - 양갈래 바이러스

문제

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

나라의 구조와 이름으로 미루어 보았을 때, 양갈래 머리를 한 사람이 많을 것이라 생각한 나나는, 갈래 나라의 국민들을 보고 충격을 받게 된다. 양갈래 머리를 한 사람이 아무도 없었던 것이다! 아무것도 모르던 시절로 돌아갈 수 없는 가슴을 찌르는 충격을 받은 나나는 무대소녀로서의 본분을 잠시 버리고 양갈래 바이러스 개발에 몰두하여 총 $Q$개 종류의 양갈래 바이러스를 제작하는데 성공하였다.

각 바이러스에는 위력 $p$와 전염력 $d$가 존재하는데, 이는 바이러스가 초기에 뿌려진 도시에서 거리가 $d$이하인 도시들은 위력이 $p$인 바이러스에 감염된다는 뜻이다. 도시 $a$에서 도시 $b$까지의 거리는 $a$에서 $b$로 가기 위해 거쳐야 하는 도로 개수의 최솟값으로 정의된다.

도시의 감염도는 나나가 모든 바이러스를 뿌린 후 현재까지 감염된 바이러스 위력의 합으로 정의된다. 하나의 도시는 2종류 이상의 바이러스에 감염될 수 있다.

나나가 모든 바이러스를 다 뿌렸을 때, 각 도시의 감염도를 출력하라.

입력

첫째 줄에 갈래 나라의 도시의 개수 $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$개의 수를 공백으로 구분하여 출력하라.

제한

힌트