Dany jest ciąg $A_1, A_2, \ldots, A_N$ o długości $N$. Napisz program wykonujący następujące zapytania:

• $1$ $i$ $j$ $x$ $y$: Dodaj ciąg arytmetyczny o pierwszym wyrazie $x$ i różnicy $y$ do $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$: Wypisz długość najdłuższego spójnego podciągu $A_l, A_{l+1}, \ldots, A_r$ takiego, że $i \le l < r \le j$ i jest on ciągiem arytmetycznym. ($1 \le i < j \le N$)

Wejście

W pierwszym wierszu podana jest długość ciągu $N$ ($2 \le N \le 100{,}000$).

W drugim wierszu znajduje się $A_1, A_2, \ldots, A_N$ ($-100{,}000 \le A_i \le 100{,}000$).

W trzecim wierszu podana jest liczba zapytań $M$ ($1 \le M \le 100{,}000$).

W kolejnych $M$ wierszach znajdują się zapytania.

Wszystkie dane wejściowe są liczbami całkowitymi.

Wyjście

Dla każdego zapytania typu $2$ wypisz odpowiedź w osobnym wierszu.

Przykład

Wejście

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

Wyjście

5
3
2