Description

There were n rows of seats in the classroom. Each row of seats littered with a_i unit of trash. 

For example: first row contained a₁ unit of trash

The janitor wanted to know how many units of trash were littered among row l to row r?

For example: If janitor ask you about row l = 3 to row r = 6. You should answer a₃ + a₄ + a₅ + a₆ unit of trash.

There will be q queries, help janitor  find out the answer so janitor  can clean up the class room.

Note that because janitor  is furious about picking up trash, each number will be follow by a symbol " (/`A`)/ ~I__I " without quotation mark and then there is a blank to separate from the next number.

Note that if you use a loop to get the sum of a_l ~ a_r at each query you will get an Time limit exceed. 

You can use prefix sum to solve this problem

Input

input contains several lines.

First line contains two integer n(1 <= n <= 10⁶), q(1 <= q <= 10⁵) -- the number of rows and the number of queries.

Second line contains n integer a₁ ~ a_n (0 <= a_i <= 10⁹), and each interger followed by a symbol " (/`A`)/ ~I__I " and then there is a blank to separate from the next number.

The following q lines each lines contains two integers l, r ( 1 <= l <= r <= n )

Output

output contain q lines, to each query output the sum of a_l ~ a_r. remember to print \n at the end of each line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Ovuvuevuevue Enyetuenwuevue Ugbemugbem Osas wants to eat watermelon. But the watermelons are stored in a cylindrical(圓柱狀) box.

---

He has n watermelons and each one has a specific index denote as a_i.

Osas wants to eat a watermelon indexed a_i.

But if the watermelon indexed a_i is not on the top,

he needs to eat all watermelon above the watermelon indexed a_i.

Osas also has a list which is the order of watermelons he wants to eat which denoted as b_i.

The length of the list is also n and all b_i are distinct.

Please help him calculate that each time he wants to eat a watermelon, how many watermelons he needs to eat at same time?

 

For example ：

if the index of watermelon from top to bottom is: 5, 3, 2, 1, 4. And the list Osas has is: 2, 3, 4, 5, 1.

First time Osas will eat 3 watermelons(5,3,2).

Second time because the watermelons that indexed 3 is already been eaten, Osas eat 0 watermelon . So on and so forth.

In this example, you need to output: 3 0 2 0 0.

 

 

Input

input contains three lines.

First line contains n the number of watermelons.( 1 <= n <= 2*10⁵ )

Second line contains n integer a₁ ~ a_n which denote as the index of watermelons from top to bottom .( 1 <= a_i <= n )

 

Third line contains n integer b₁ ~ b_n which denote as the order of watermelons  that Osas' wants to eat.( 1 <= b_i <= n )

 

Output

output contains one line.

output n integer means the number of watermelons that each time Osas eat. Separate each number by a blank but don't print the blank after the last number.

remember to print \n at the end of output.

 

Sample Input  Download

Sample Output  Download

Tags

Discuss