Maxstack

Time limit: 0.6s Memory limit: 512MB Input: Output:

We define the following two operations which can be performed on a stack:

  • push(x)push(x) — the number xx is added to the top of the stack
  • poppop — the number on top of the stack is removed from the stack.

A sequence of operations is considered to be correct if, when the operations are performed on an initially empty stack in order, the following two conditions are met:

  1. No pop operation is performed on an empty stack,
  2. After the last operation, the stack is empty.

For example, (push(1), pop)(push(1), \ pop) is correct, whereas (push(1), push(2))(push(1), \ push(2)), or (pop, push(1))(pop, \ push(1)) are not.

We will consider a list L1,,LNL_1, \dots , L_N of operations, numbered from 11 to NN. By s(i,j)s(i, j), where iji ≤ j, we denote the sequence of operations Li,Li+1,,LjL_i, L_{i+1}, \dots , L_j.

We define the value maxstack(i,j)maxstack(i, j) as follows. If s(i,j)s(i, j) is not a correct sequence, then we define maxstack(i,j)=0maxstack(i, j) = 0. Otherwise, we perform the operations Li,Li+1,,LjL_i, L_{i+1}, \dots , L_j in order on an initially empty stack. After each operation, we calculate the maximum value in the stack. Let mkm_k be the maximum value after operation kk, or zero if the stack is empty. Then, maxstack(i,j)=mi+mi+1++mjmaxstack(i, j) = m_i + m_{i+1} + \dots + m_j.

Task

You are given NN, the list LL of operations, a number QQ, and QQ queries of the form (l,r)(l, r), where 1lrN1 ≤ l ≤ r ≤ N. You are also given a number CC. Depending on the value of CC, you must calculate the following for all queries:

  1. If C=1C = 1, then you should calculate maxstack(l,r)maxstack(l, r) modulo 109+710^9 + 7. It is guaranteed that s(l,r)s(l, r) is correct for all queries.
  2. If C=2C = 2, then you should calculate the sum of maxstack(i,j)maxstack(i, j) for all lijrl ≤ i ≤ j ≤ r modulo 109+710^9 + 7. It is guaranteed that for every query, if you perform the operations of s(l,r)s(l, r) in order, then no pop operation is performed on an empty stack.

Input data

The first line of input contains the value CC. The second line contains the integers NN and QQ. The third line contains non-negative integers X1,X2,,XNX_1, X_2, \dots , X_N which encode L1,,LNL_1, \dots , L_N as follows:

  • If Xi>0X_i > 0, then Li=push(Xi)L_i = push(X_i)
  • If Xi=0X_i = 0, then Li=popL_i = pop

Each of the following QQ lines contains two integers ll and rr, representing the queries.\

Output data

Each of the QQ lines of output should contain the answers to the queries, in order. All answers must be given modulo 109+710^9 + 7.

Restrictions

  • 1N,Q300 0001 \leq N, Q \leq 300 \ 000
  • 0Xi1090 \leq X_i \leq 10^9, for all 1iN1 \leq i \leq N
  • L1,,LNL_1, \dots , L_N is guaranteed to be a correct sequence of operations
  • We call a sequence of operations finally empty if, when performing these operations on an empty stack, the stack is empty only before the first operation and after the last one. For example, (push(1), pop)(push(1), \ pop) is finally empty, but (push(1), pop, push(1), pop)(push(1), \ pop, \ push(1), \ pop) is not.
# Points Restrictions
1 7 C=1,N,Q100C = 1, N, Q \leq 100
2 14 C=1,N,Q100C = 1, N, Q \leq 100
3 15 C=1,Xi30C = 1, X_i \leq 30 and s(l,r)s(l, r) is finally empty for every query (l,r)(l, r)
4 13 C=1C = 1
5 14 C=2,s(l,r)C = 2, s(l, r) is correct and finally empty for every query (l,r)(l, r)
6 11 C=2,s(l,r)C = 2, s(l, r) is correct for every query (l,r)(l, r)
7 10 C=2,N70 000,Q50C = 2, N \leq 70 \ 000, Q \leq 50
8 11 C=2,N,Q70 000C = 2, N, Q \leq 70 \ 000
9 5 C=2C = 2

Example 1

stdin

1
6 2
5 4 0 0 23 0
1 4
5 6

stdout

15
23

Explanation

For the first query, we will perform the operations from 11 to 44 in order. After the first operation, the stack looks like this: (5)(5). m1=5m_1 = 5. After the second operation, the stack looks like this: (5,4)(5, 4). m2=5m_2 = 5. After the third operation, the stack looks like this: (5)(5). m3=5m_3 = 5. After the last operation, the stack is empty. m4=0m_4 = 0. m1+m2+m3+m4=5+5+5+0=15m_1 + m_2 + m_3 + m_4 = 5 + 5 + 5 + 0 = 15.

For the second query, we must perform operations 55 and 66. After operation 55, the stack looks like this: (23)(23). m5=23m_5 = 23. After the last operation, the stack is empty. m6=0m_6 = 0. m5+m6=23+0=23m_5 + m_6 = 23 + 0 = 23.

Example 2

stdin

1
10 4
22 0 26 0 72 447 0 497 0 0
1 10
3 10
8 9
1 4

stdout

1208
1186
497
48

Explanation

For the first query, m1++m10=22+0+26+0+72+447+72+497+72+0=1208.m_1 + \dots + m_{10} = 22 + 0 + 26 + 0 + 72 + 447 + 72 + 497 + 72 + 0 = 1208.

For the second query, m3++m10=26+0+72+447+72+497+72+0=1186.m_3 + \dots + m_{10} = 26 + 0 + 72 + 447 + 72 + 497 + 72 + 0 = 1186.

For the third query, m8+m9=497+0=497.m_8 + m_9 = 497 + 0 = 497.

For the last query, m1+m2+m3+m4=22+0+26+0=48.m_1 + m_2 + m_3 + m_4 = 22 + 0 + 26 + 0 = 48.

Example 3

stdin

2
10 5
22 0 26 0 72 447 0 497 0 0
1 10
3 10
8 9
1 4
1 9

stdout

5538
4260
497
96
1984

Explanation

The values of maxstack for all subsequences (i,j)(i, j) are written in the table below. We leave the cells where i>ji > j (for which the operation is not defined) empty.

ji_{j} \diagdown ^{i} 11 22 33 44 55 66 77 88 99 1010
11 00
22 2222 00
33 00 00 00
44 4848 00 2626 00
55 00 00 00 00 00
66 00 00 00 00 00 00
77 00 00 00 00 00 447447 00
88 00 00 00 00 00 00 00 00
99 00 00 00 00 00 944944 00 497497 00
1010 12081208 00 11861186 00 11601160 00 00 00 00 00

Log in or sign up to be able to send submissions!