Andryusha and Nervous Barriers
Contest: Технокубок 2017 - Финал (только для онсайт-финалистов)
Difficulty rating: 2700
Tags: data structures, dp

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 li through ri of the row ui. 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 si (that is, it started its fall strictly higher than ui + si), 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 109 + 7.

Input format:
The first line contains three integers h, w, and n (1 ≤ h ≤ 109, 2 ≤ w ≤ 105, 0 ≤ n ≤ 105) — the number of rows, columns, and barriers in the machine respectively.

Next n lines describe barriers. i-th of these lines containts four integers ui, li, ri, and si (1 ≤ ui ≤ h, 1 ≤ li ≤ ri ≤ w, 1 ≤ si ≤ 109) — 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 ui are distinct.

Output format:
Print one integer — the answer to the problem modulo 109 + 7.

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

Note:
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.

Example input:
10 5 1
3 2 3 10

Example output:
7

Example input:
10 5 2
3 1 3 10
5 3 5 10

Example output:
16

Editorial:
Solution 1: Let us move a sweep-line from the bottom to the top, and say that i-th barrier is active if the current y-coordinate satisfies ui ≤ y ≤ ui + si. If we want to find the result of dropping a ball in column x at a certain moment, we have to find the highest active barrier that covers x at the moment.
Let us store a segment tree, with a set of active segments in each tree node. When introducing a new active segment, we represent it as a union of $${\mathcal O}\left(\log w\right)$$ tree nodes, and add this segment in each of these nodes' set; when a segment becomes non-active, we delete these entries. If at any point we are interested in finding the highest active barrier for a column x, we consider all $${\mathcal O}\left(\log w\right)$$ tree nodes covering x and look at their highest entries only. Also, for each segment we store the number of resulting balls after hitting this segment; this number can be found by making two queries to the tree (for the two balls resulting from the collision) at the same time we activate the barrier.
To find the final answer, for each column drop a ball in it from height h + 1 and sum the results. Thus, the answer can be found in $${ \mathcal { O } } ( ( n + w ) \log ^ { 2 } w )$$ time (with the second logarithm for std::set working time).
Solution 2: Let us go from the top to the bottom instead, and maintain positions of all balls to be dropped. If any of these balls occupy the same position, we group them together and store the size of the group. Each column will have a separate stack of groups, with lower groups on top of the stack.
Let's see how a new barrier [l, r] changes our configuration. For each column [l, r] we want to drop several lowest groups on the barrier, which will result in creating at most two new groups next to the barrier. Let us store a segment tree of size w, with x-th entry equal to the height of the lowest group in column x. While [l, r] range minimum in the segment tree is low enough, we pop the lowest group from the corresponding stack (and update the segment tree accordingly). Finally, we create the new groups, and push them to their respective stacks. After processing all barriers, the rest groups will fall straight to the bottom.
A standard amortized estimate shows that O(n + w) operations will be performed, for $${ \mathcal { O } } \left( ( n + w ) \log w \right)$$ time complexity.