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)$的位置都释放了一个球，你想要知道，最后一共有多少个球掉落到最底部了。 输入格式 第一行输入三个整数$h,w,n(1\leq h\leq 10^9)$ 接下来$n$行，每行输入四个整数$u_i,l_i,r_i,s_i(1\leq u_i\leq h,1\leq l_i\leq r_i\leq w,s_i\leq 10^9)$，描述一个隔板。 输出格式 一行，一个整数，代表答案对$10^9+7$取模的结果。

题目描述

Andryusha has found a perplexing arcade machine. The machine is a vertically adjusted board divided into square cells. The board has $ w $ columns numbered from $ 1 $ to $ w $ from left to right, and $ h $ rows numbered from $ 1 $ to $ h $ from the bottom to the top. Further, there are barriers in some of board rows. There are $ n $ barriers in total, and $ i $ -th of them occupied the cells $ l_{i} $ through $ r_{i} $ of the row $ u_{i} $ . Andryusha recollects well that no two barriers share the same row. Furthermore, no row is completely occupied with a barrier, that is, at least one cell in each row is free. The player can throw a marble to any column of the machine from above. A marble falls downwards until it encounters a barrier, or falls through the bottom of the board. A marble disappears once it encounters a barrier but is replaced by two more marbles immediately to the left and to the right of the same barrier. In a situation when the barrier is at an edge of the board, both marbles appear next to the barrier at the side opposite to the edge. More than one marble can occupy the same place of the board, without obstructing each other's movement. Ultimately, all marbles are bound to fall from the bottom of the machine. Examples of marble-barrier interaction.Peculiarly, sometimes marbles can go through barriers as if they were free cells. That is so because the barriers are in fact alive, and frightened when a marble was coming at them from a very high altitude. More specifically, if a marble falls towards the barrier $ i $ from relative height more than $ s_{i} $ (that is, it started its fall strictly higher than $ u_{i}+s_{i} $ ), then the barrier evades the marble. If a marble is thrown from the top of the board, it is considered to appear at height $ (h+1) $ . Andryusha remembers to have thrown a marble once in each of the columns. Help him find the total number of marbles that came down at the bottom of the machine. Since the answer may be large, print it modulo $ 10^{9}+7 $ .

输入输出格式

输入格式

The first line contains three integers $ h $ , $ w $ , and $ n $ ( $ 1<=h<=10^{9} $ , $ 2<=w<=10^{5} $ , $ 0<=n<=10^{5} $ ) — the number of rows, columns, and barriers in the machine respectively. Next $ n $ lines describe barriers. $ i $ -th of these lines containts four integers $ u_{i} $ , $ l_{i} $ , $ r_{i} $ , and $ s_{i} $ ( $ 1<=u_{i}<=h $ , $ 1<=l_{i}<=r_{i}<=w $ , $ 1<=s_{i}<=10^{9} $ ) — row index, leftmost and rightmost column index of $ i $ -th barrier, and largest relative fall height such that the barrier does not evade a falling marble. It is guaranteed that each row has at least one free cell, and that all $ u_{i} $ are distinct.

输出格式

Print one integer — the answer to the problem modulo $ 10^{9}+7 $ .

输入输出样例

输入样例 #1

10 5 1
3 2 3 10

输出样例 #1

7

输入样例 #2

10 5 2
3 1 3 10
5 3 5 10

输出样例 #2

16

输入样例 #3

10 5 2
3 1 3 7
5 3 5 10

输出样例 #3

14

输入样例 #4

10 15 4
7 3 9 5
6 4 10 1
1 1 4 10
4 11 11 20

输出样例 #4

53

说明

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.

题意翻译

题目描述 你在玩一个游戏：游戏的界面是一个网格，高度为$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)$的位置都释放了一个球，你想要知道，最后一共有多少个球掉落到最底部了。 输入格式 第一行输入三个整数$h,w,n(1\leq h\leq 10^9)$ 接下来$n$行，每行输入四个整数$u_i,l_i,r_i,s_i(1\leq u_i\leq h,1\leq l_i\leq r_i\leq w,s_i\leq 10^9)$，描述一个隔板。 输出格式 一行，一个整数，代表答案对$10^9+7$取模的结果。