K. Kiere Volar
time limit per test
1.5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Leonardo Javier "El Chicharito" Toral Hernández had always wanted to watch his beloved Cruz Azul play. Unfortunately, that year Mexico was hosting the World Cup, forty years after the previous tournament held there in 1986. Jorge convinced Leonardo that supporting Mexico had to come before supporting Cruz Azul, so he invited him to the FanFest to watch Mexico play against England.

Everyone was enjoying the match, which Mexico seemed to dominate. However, England eventually took the lead, and Leonardo even wanted to enter the field in place of Memote Martínez. Jorge stopped him—although perhaps he should not have.

The FanFest was divided into $$$n$$$ rows, numbered from $$$1$$$ to $$$n$$$. Initially, row $$$i$$$ contained $$$a_i$$$ fans wearing Mexico jerseys.

During the event, more fans could join the celebration. In one operation, the organizers brought $$$x$$$ new fans to every row from $$$l$$$ to $$$r$$$.

For promotional pictures, the organizers could select a range of rows from $$$l$$$ through $$$r$$$ and ask the fans to perform a routine called "Quiere Volar". In each selected row, all fans had to be divided into groups of size $$$g$$$. The same value of $$$g$$$ had to be used for every selected row. Fans from different rows could not be mixed, and no fan could be left out.

For every promotional picture query, determine the maximum possible value of $$$g$$$.

Input

The first line contains two integers $$$n$$$ and $$$q$$$, the number of rows and the number of operations.

The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$, where $$$a_i$$$ is the initial number of fans in row $$$i$$$.

Each of the next $$$q$$$ lines describes one operation. An operation is one of the following:

  • 1 l r x: add $$$x$$$ fans to every row $$$i$$$ such that $$$l \le i \le r$$$.
  • 2 l r: take a promotional picture using rows $$$l$$$ through $$$r$$$, and determine the maximum possible group size $$$g$$$.

It is guaranteed that $$$1 \le n,q \le 5\cdot 10^5$$$, $$$1 \le a_i \le 10^9$$$ for every $$$i$$$, $$$1 \le x \le 10^9$$$ in every operation of type $$$1$$$, and $$$1 \le l \le r \le n$$$ for every operation. All row sizes fit in signed 64-bit integers.

Output

For every operation of type $$$2$$$, print one line containing the maximum possible group size.

Example
Input
5 6
1 3 6 9 15
2 1 5
1 2 4 3
2 2 4
1 1 2 1
2 1 3
2 3 5
Output
1
3
1
3
Note

The first query has answer $$$1$$$. After the first update, rows $$$2$$$, $$$3$$$, and $$$4$$$ contain $$$6$$$, $$$9$$$, and $$$12$$$ fans, respectively. The second query groups them independently into groups of size $$$3$$$.