Description

Given a series of numbers, e₁, e₂, e₃, ..., e_N.

With these numbers, we want to know what the sum is in some consecutive range.

In every testcase, you will be given M queries.

Each of them contains two integers which represent left bound (L) and right bound (R) respectively.

Your mission is to give the result of e_L + e_L+1 + ... + e_R,

-

Hint 0 : If you get WA for testcase 1, sample input and output might help you.

Hint 1 : If you get TLE for next three testcases, you should think how to decrease some redundant operations for calculations. Try to store other useful information in the array, instead of sum up all the elements for every query! You may search for the problem's title: "prefix sum".

Hint 2 : If you get MLE, you have to reduce the size of array you created and decide what exactly should be in the array.

Input

First line contains one integer N which is the size of elements.

Second line will have N integers representing all elements in the testcase.

Third line contains one integer M which is the number of queries.

For following M lines, each line contains exactly two integers that stand for left bound (L) and right bound (R) respectively.

It is guaranteed that:

1. 10 ≦ N ≦ 1,000,000

2. 0 ≦ e_i ≦ 100,000, for 1 ≦ i ≦ N

3. L must be less than or equal to R, and R won't exceed the size of elements.

Output

For each query, just give the answer in one line.

Also, remember to print '\n' in the end of line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

You are given a n x m matrix a. Each time you can rotate it 90 degrees in clockwise direction.

For example, let's consider a is a 3 x 2 matrix where   .

After we rotate it once, it will become a' where .

Your task is to rotate a for q times.

Input

The first line contains two integer n, m (1 ≤ n, m ≤ 100) – the number of rows and the number columns in matrix a.

The following n lines contain m integers each, the j-th element in the i-th line is a_ij (1 ≤ a_ij ≤ 10⁹).

Next line contain a integer q (1 ≤ q ≤ 10⁹) – the times you have to rotate a.

Output

Output a after rotating it for q times.

There must be exactly a space between all the adjacent numbers in the same row.

And print a newline('\n') at the end of each line.

Remember not to print any space at the end of any line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Pekotrick and Patruto are good friends. In the universe where Pekotrick and Patruto lived, one year have 12 months, one month is always 30 days, and there are 24 hours a day, 60 minutes per hour and 60 seconds per minute. Today, your TA in Introduction to programming (I) accidently know that they born in the same year, so he is curious about how much the birth time difference is between Pekotrick and Patruto. But your TA is too tired to calculate the difference. Can you write a program to help your TA? 

Hint:
You can get the hint in the chorus of the song below in the link.
https://www.youtube.com/watch?v=TVOVed8q_pQ
If you think that this hint is useless or you can't get the point about what it's talking about, you can just ignore it XD.

Input

Input contains two lines, first line is the time when Pekotrick borned, second line is the time when Patruto borned.

Each line meets the format below:

Month/day hh:mm:ss

Month/day represent the date, and hh:mm:ss represent the 24-hour clock time.

Output

Output the birth time difference between Pekotrick and Patuto in the following format.

Month day
hh:mm:ss

The format below represents how many Month, day, hour, minute, second difference in birth time between Pekotrick and Patuto.

You need to fill each element in 24-hour clock time with 2 digits. That is, you have to output "01:20:06" instead of "1:20:6".

And you have to complete the carry, that is, for one day, 6 hours and 20 minutes, you have to output: 

0 1
06:20:00

instead of

0 0
00:1820:00

(1 day, 6 hours, 20 minutes is equal to 1820 minutes)
Remember to add '\n' at the end of everyline.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

You are given a string s whose length is n. And s consists of only numbers except 0.

In this problem s_i represents the i-th character in s and s is 0 based indexing.​ And we call a substring s[l...r) of s is a string s_l s_l+1 s_l+2 ... s_r-1 (i.e. the concatenation of s_l, s_l+1, s_l+2, ..., s_r-1 in the order).

Now you have to execute the folloing operation on s for q times.

In each operation, you are given three numbers a, b and sz. And then:

1. Let A = s[a...a+sz) and B = s[b...b+sz)
2. Remove A and B from s simultaneously.
3. Consider A and B as numbers. Then output the product of A x B.

For example suppose s = "3124561245" whose length is n = 10. And q = 2.

In the first operation, consider a = 0, b = 1 and sz = 1. So A = s[a,a+sz) = s[0,1) = "3" and B = "1". s will become "24561245" after removing A and B from it. Afterwards we output the product of A x B = 3 x 1 = 3.

In the second operation, consider a = 1, b = 4 and sz = 2. So A = "45" and B = "12". s will become "2645" after removing A and B from it. Finally we output the product of A x B = 45 x 12 = 540.

Input

The first line contains an integer n (1 ≤ n ≤ 1000) – the length of s.

Next line contains the string s (|s| = n) which consists of only numbers except 0.

The third line contains one integer q (1 ≤ q ≤ 1000) – the times you have to execute operation on s.

Then q lines follow. Each line contains three integers a, b, sz (1 ≤ sz ≤ 9, 0 ≤ a < a+sz ≤ b < b+sz ≤ |s|) – the range of the two substring A and B.

It is guaranteed that all the operations are valid. That is you can always remove A and B from s successfully.

Output

For each operation you execute on s, output the product of A x B.

And print a newline('\n') at the end of each line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given an integer sequence, you are asked to compute how many pairs are there in the sequence.

Pair definition: if sequence[a] =  sequence[b] and a < b, then sequence[a] and sequence[b] are pairs. (a , b are index)

For example:

Input sequence = 1 2 4 1 9 7 2 3 1 8

There are 4 pairs which index pairs are (0, 3), (0, 8), (1, 6), (3, 8) in this sequence .

Input

First line contains an integer N which denotes the length of the input sequence. (1 ≤ N ≤ 100000)

Second line contains N integer which denote the input sequence. (0 ≤ each number in input sequence ≤ 10000)

Output

An integer which denote the number of pairs in the sequence.

Remember to print a newline('\n') at the end of the last line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given a board with N rows and M columns, the rows are numbered from 1 to N from top to bottom, and the columns are numbered from 1 to M from left to right. Each element has one diagonal wall which either runs from top-left corner to bottom-right corner, or runs from top-right corner to bottom-left corner. Now given Q queries, you have to output which column the ball will fall out at the bottom row if you put it on top of the board at specific column. (The ball will naturally fall down due to gravity.)

The following figure is a sample. If you drop the ball at column 2, the ball will fall out at the left side. If you drop the ball at column 5, the ball will stuck in the board. If you drop the ball at column 3, the ball will eventually fall out at column 2.

Input

First line contains two integers which represent n, m respectively. (1 <= n, m <= 500).

The following N lines which have M characters in each line represent the board. '/' means the wall runs from top-right corner to bottom-left corner, and '\' means the wall runs from top-left corner to bottom-right corner.

Next line contains an integer Q which denotes the number of querys. (1 <= Q <= 100).
Then, the following Q line, each line has one integer which represents the starting column to drop the ball.

Output

For each queries:
If the ball fall out at the right side, you should output "Right!".
If the ball fall out at the left side, you should output "Left!".
If the ball stuck at the board, you should output "Stuck QQ".
Otherwise, you should output "Position: x". x represents which column the ball fall out at the bottom row.
Remember to output '\n' at the end of each line.

Sample Input  Download

Sample Output  Download

Tags

Discuss