You are given a sequence $A_1, A_2, \ldots, A_N$ of length $N$. Write a program that processes the following queries:

• $1$ $i$ $j$ $x$ $y$ : Add an arithmetic progression with first term $x$ and common difference $y$ to $A_i, A_{i+1}, \ldots, A_j$. ($1 \le i \le j \le N$, $-100{,}000 \le x, y \le 100{,}000$)
• $2$ $i$ $j$ : Output the length of the longest contiguous subarray $A_l, A_{l+1}, \ldots, A_r$ that forms an arithmetic progression, where $i \le l < r \le j$. ($1 \le i < j \le N$)

Input

The first line contains $N$ ($2 \le N \le 100{,}000$), the length of the sequence.

The second line contains $A_1, A_2, \ldots, A_N$. ($-100{,}000 \le A_i \le 100{,}000$)

The third line contains $M$ ($1 \le M \le 100{,}000$), the number of queries.

The next $M$ lines each contain a query.

All input values are integers.

Output

For each type 2 query, output the answer on a separate line.

Examples

Input 1

5
1 2 3 4 5
4
2 1 5
1 3 4 1 1
2 1 5
2 3 5

Output 1

5
3
2