CF780G Andryusha and Nervous Barriers

你在玩一个游戏：游戏的界面是一个网格，高度为$h$，宽度为$w$，玩家可以从网格正上方（高度为$h+1$）的位置释放小球。 网格中有$n$个水平隔板，第$i$个隔板高度为$u_i$，挡住了$[l_i,r_i]$这段区间。没有两个隔板位于同一高度。当球落到隔板上的时候，球会分裂成两个球，分别从隔板的左右（$l_i=1$和$r_i+1$）掉落。特别地，如果隔板与网格的左右边缘挨着，则生成的两个球都会在不与网格边缘挨着的位置掉落。 但是，球不一定会落到隔板上。当球的速度过快时，它可能会直接穿过隔板。具体地，对于隔板$i$，如果球在到达隔板前所掉落的高度严格大于$s_i$（即，从严格大于$u_i+s_i$的高度开始掉落），它就会直接穿过隔板，同样也不会分裂。你在每个坐标为$(h+1,i)$的位置都释放了一个球，你想要知道，最后一共有多少个球掉落到最底部了。

无

无

In the first sample case, there is a single barrier: if one throws a marble in the second or the third column, two marbles come out, otherwise there is only one. The total answer is $ 7 $ . In the second sample case, the numbers of resulting marbles are $ 2 $ , $ 2 $ , $ 4 $ , $ 4 $ , $ 4 $ in order of indexing columns with the initial marble. In the third sample case, the numbers of resulting marbles are $ 1 $ , $ 1 $ , $ 4 $ , $ 4 $ , $ 4 $ . Note that the first barrier evades the marbles falling from the top of the board, but does not evade the marbles falling from the second barrier. In the fourth sample case, the numbers of resulting marbles are $ 2 $ , $ 2 $ , $ 6 $ , $ 6 $ , $ 6 $ , $ 6 $ , $ 6 $ , $ 6 $ , $ 6 $ , $ 1 $ , $ 2 $ , $ 1 $ , $ 1 $ , $ 1 $ , $ 1 $ . The picture below shows the case when a marble is thrown into the seventh column. The result of throwing a marble into the seventh column.