Description

There are three functions:

f(x) = 7x + 1

g(x, y) = 4x + 9y - 2

h(x, y, z) = x - 3y + z - 9

You will be given a expression of these three functions.

For example:

h g f 1 4 1 f 2

which represent:

h(g(f(1), 4), 1, f(2))

= h(g(8, 4), 1, 15)

= h(66, 1, 15)

= 69

Input

A single line with numbers of characters, all the characters are separated with a whitespace.

It is guarantee that the characters contains only f g h and numbers from 0 to 9.

It is guarantee that all the number throughout the entire calculation won't exceed the range of long long.

It is guarantee that the number of characters (excluding whitespace) won't exceed 100.

There won't be any - .

There won't be any adjacent numbers, which means all the numbers are single-digit.

To be clear, the following examples won't appear in the testcase.

h g f 1 4 1 f 23 (two-digit number 23)

h g f -1 4 1 f 2 (negative number -1)

Output

Output the answer of the given expression.

Note that you do NOT need to print '\n' at the end of the output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

There are K treasures hidden deep under the river, and you accidently got a map for these secret treasures.

The map doesn't told you where these treasures were exactly, but it does give you some hint:

We can think of the river as a 1D structure and divided it into N chunks.

The i-th chunk is assigned to a lucky number Ai.

Then, the map gives you some intervals [L, R].

Each interval indicate a secret treasure, and it is hidden in the luckiest chunk in that interval.

The luckiest chunk is defined as following, for an interval [L, R] :

1. If L == R, the luckiest chunk is that single chunk L.
2. If L < R, find the middle chunk M = (L+R) / 2, then divide the interval into two segment [L, M-1], [M+1, R], and calculate the sum of each segment. The luckest chunk is at the segment with the larger sum.
   • If two segments have the same sum, then the luckest chunk is at the segment [M+1, R].
   • If a segment contains no numbers (L > M-1 or M+1 > R), then the sum of that segment is 0.

Take the sample input output as an example:

There are three intervals to search for:

For the first interval, L = 1, R = 5, hence M = (1+5)/2 = 3.

Then divide the interval into two segments and calculate their sum:

1. L = 1, R = 2, sum = 14
2. L = 4, R = 5, sum = 5

Since the segment 1 has the largest sum 14, the luckest chunck is in that segment and we continue search in that segment.

Now, L = 1, R = 2, hence M = (1+2)/2 = 1.

Then divide the interval into two segments and calculate their sum:

1. L = 1, R = 0, sum = 0
2. L = 2, R = 2, sum = 10

Since the segment 2 has the largest sum 10, the luckest chunck is in that segment and we continue search in that segment.

Now, L = 2, R = 2, since L == R, the luckiest chunk is chunk 2, and the lucky number of that chunk is 10.

--------------------------------------------------------------------------------

For the second interval, L = 4, R = 7, hence M = (4+7)/2 = 5.

Then divide the interval into two segments and calculate their sum:

1. L = 4, R = 4, sum = 3
2. L = 6, R = 7, sum = 17

Since the segment 2 has the largest sum 17, the luckest chunck is in that segment and we continue search in that segment.

Now, L = 6, R = 7, hence M = (6+7)/2 = 6.

Then divide the interval into two segments and calculate their sum:

1. L = 6, R = 5, sum = 0
2. L = 7, R = 7, sum = 8

Since the segment 2 has the largest sum 8, the luckest chunck is in that segment and we continue search in that segment.

Now, L = 7, R = 7, since L == R, the luckiest chunk is chunk 7, and the lucky number of that chunk is 8.

--------------------------------------------------------------------------------

For the third interval, L = 6, R = 6, since L == R, the luckiest chunk is chunk 6, and the lucky number of that chunk is 9.

 

Input

The first line contains two integers N, K, represent the number of the chunks and the number of the treasures.

Next, there would be N lines, each line contains a integers Ai, represents the lucky number of chunk i.

Next, there would be K lines, each line contains two integers Li, Ri, represent the interval i.

For testcase 1~5:

1 ≤ N, K ≤ 1000

For testcase 6:

1 ≤ N, K ≤ 200000

0 ≤ Ai ≤ 10000

Output

Output K lines, each line contains an integer representing the lucky number of luckiest chunk of the i-th interval.

Note that you NEED to print '\n' at the end of the output.

Sample Input  Download

Sample Output  Download

Tags

Discuss