4036：完全k叉树

有一颗包含$$n$$个节点的完全$$k$$叉树，这些节点的编号为$$1$$到$$n$$。

具体编号规则如下：对于一颗有$$n$$个节点的完全$$k$$叉树，根节点的编号为$$1$$，然后按从上至下，从左到右的顺序依次为其它节点进行编号。

接下来会进行$$m$$次操作，操作格式有以下两种：

①$$1\ x\ y$$：从编号为$$x$$的节点到根节点路径上所有的节点权值加$$y$$。

②$$0\ x\ y$$：把除了 “从编号为$$x$$的节点到根节点路径上所有的节点” 以外的节点权值加$$y$$。

输出在$$m$$次操作之后每个结点的权值。

第一行输入树的结点个数$$n$$，操作的次数$$m$$，树是完全$$k$$叉树。（$$1 \leq n,m \leq 10^5$$，$$2 \leq k \leq 10^5$$）

然后$$m$$行，每行是一个描述中给出的操作，其中$$1 \leq x \leq n$$，$$0 \leq y \leq 2 \times 10^6$$。

输出每个节点的权值，每个值输出后都带空格。

10 2 2

1 10 1

0 3 100

1 101 0 100 101 100 100 100 100 101 

样例中的树如下图：

TKK寒假赛Round#11

题单#17（树和图的存储与遍历）