Osu 听过没？那是 Konano 最喜欢的一款音乐游戏，而他的梦想就是有一天自己也能做个独特酷炫的音乐游戏。现在，他在世界知名游戏公司 KONMAI 内工作，离他的梦想也越来越近了。
这款音乐游戏内一般都包含了许多歌曲，歌曲越多，玩家越不易玩腻。同时，为了使玩家在游戏上氪更多的金钱花更多的时间，游戏一开始一般都不会将所有曲目公开，有些曲目你需要通关某首特定歌曲才会解锁，而且越晚解锁的曲目难度越高。
这一天，Konano 接到了一个任务，他需要给正在制作中的游戏《IIIDX》安排曲目的解锁顺序。游戏内共有 n n n 首曲目，每首曲目都会有一个难度 d d d，游戏内第 i i i 首曲目会在玩家 Pass 第 ⌊ i k ⌋ \left\lfloor \frac i k \right\rfloor ⌊ki⌋ 首曲目后解锁（ ⌊ x ⌋ \left\lfloor x \right\rfloor ⌊x⌋ 为下取整符号）若 ⌊ i k ⌋ = 0 \left\lfloor \frac i k \right\rfloor = 0 ⌊ki⌋=0，则说明这首曲目无需解锁。
举个例子：当 k = 2 k = 2 k=2 时，第 1 1 1 首曲目是无需解锁的（ ⌊ 1 2 ⌋ = 0 \left\lfloor \frac 12 \right\rfloor = 0 ⌊21⌋=0），第 7 7 7 首曲目需要玩家 Pass 第 ⌊ 7 2 ⌋ = 3 \left\lfloor \frac 72 \right\rfloor = 3 ⌊27⌋=3 首曲目才会被解锁。
Konano 的工作，便是安排这些曲目的顺序，使得每次解锁出的曲子的难度不低于作为条件需要玩家通关的曲子的难度，即使得确定顺序后的曲目的难度对于每个 i i i 满足 d i ≥ d ⌊ i k ⌋ d_i \geq d_{\left\lfloor \frac ik \right\rfloor} di≥d⌊ki⌋。
1 ≤ n ≤ 5 × 1 0 5 , 1 ≤ k , d ≤ 1 0 9 1 \le n \le 5 \times 10^5,1 \le k,d \le 10^9 1≤n≤5×105,1≤k,d≤109
(此处省略错误贪心)
转化成有根树，然后考虑从 1 ∼ n 1 \sim n 1∼n 放数，将 d d d 从大到小排序。
对于每个数 x x x ，我们想要其最大，所以我们可以设 f i f_i fi 为 i i i 前还能放的位置，然后找到最靠前的 i i i ，使得 m i n { f j } ( j ∈ [ i , n ] ) ≥ s i z e x min\{f_j\}(j \in [i,n]) \ge size_x min{fj}(j∈[i,n])≥sizex 即可，然后找到和 i i i 相同的数的最后一个位置 j j j ，将 [ j , n ] [j,n] [j,n] 的位置的 f f f 都减去 s i z e x size_x sizex 即可，这些操作用线段树维护即可。
注意要把父亲的 s i z e size size 加回来
