Walk Alone planted magical carrot trees in a row. Let denote the number of carrots on the -th tree (note that is a real number). Initially, there are no carrots on any tree. On each day, he can do one of the following two operations on the trees:

• . Water all carrot trees between and inclusively. After that, will increase by immediately for all , where is a constant in all operations.

• . Pick a carrot from all trees between and inclusively and having at least one carrot. After that, will decrease by for all integers where and .

After days, Walk Alone has picked many carrots, and he wants you to tell him the total number of carrots he harvested.

The first line contains three integers ,  and , indicating the number of carrots, the number of operations, and the constant in the first operation.
Each of the following  lines indicates an operation, the format of which is as above. It is guaranteed that  and .

Output an integer indicating the total number of carrots.

5 5 3
1 1 3 4
2 2 4
1 1 2 3
1 4 5 3
2 1 4

5