E. Millionaire
time limit per test
2.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is an interactive problem.

A millionaire decided to open $$$N$$$ accounts in the bank to store his money. The accounts are numbered from $$$1$$$ to $$$N$$$. Each account can hold any integer amount of money (including negative values). The bank supports three types of operations:

  1. $$$l$$$ $$$r$$$ $$$c$$$ — Add the value $$$c$$$ to the accounts numbered $$$l$$$, $$$l+1$$$, ..., $$$r$$$;
  2. $$$d$$$ $$$c$$$ — Add the value $$$c$$$ to the accounts numbered $$$d$$$, $$$2d$$$, $$$3d$$$, ...;
  3. $$$l$$$ $$$r$$$ — Get the total amount of money in the accounts $$$l$$$, $$$l+1$$$, ..., $$$r$$$.

The millionaire has many accounts and plans to use them actively, but he fears that the banking system may not handle his requests efficiently. Help the bank by writing a program that efficiently executes all the required operations.

Input

The first line of input contains a single integer $$$N$$$ ($$$1 \le N \le 10^5$$$) — the number of accounts. The second line contains $$$N$$$ integers $$$a_1, a_2, ..., a_N$$$ ($$$|a_i| \le 10^9, 1 \leq i \le N$$$) — the initial amounts of money in each account. The third line contains the integer $$$M$$$ ($$$1 \le M \le 10^5$$$) — the number of operations. The next $$$M$$$ lines describe the operations. The first number indicates the type of operation.

If the type is 1, it is followed by three numbers $$$l$$$, $$$r$$$, $$$c$$$ ($$$1 \le l \le r \le N, |c| \le 10^4$$$).

If the type is 2, it is followed by two numbers $$$d$$$, $$$c$$$ ($$$1 \le d \le N, |c| \le 10^4$$$).

If the type is 3, it is followed by two numbers $$$l$$$, $$$r$$$ ($$$1 \le l \le r \le N$$$).

Output

For each operation of the third type, output the total amount of money in the specified accounts.

Interaction

Initially, the program will output the number of accounts and the initial amounts of money in them. After that, the program will output a number representing the number of operations and the operations themselves. After each operation of the third type, you need to output the answer to it, and only after that will you have access to information about the next operations.

Example
Input
10
1 2 3 4 5 6 -2 -3 -4 -5
9
3 4 8
1 7 10 2
3 7 10
2 2 -2
3 1 6
2 3 2
2 5 -7
1 2 8 4
3 3 10
Output
10
-6
15
20
Note

In the example, after the second operation, the amounts in the accounts will be as follows:     1 2 3 4 5 6 0 -1 -2 -3     After the fourth operation:     1 0 3 2 5 4 0 -3 -2 -5     After the sixth operation:     1 0 5 2 5 6 0 -3 0 -5     After the seventh operation:     1 0 5 2 -2 6 0 -3 0 -12     After the eighth operation:     1 4 9 6 2 10 4 1 0 -12