Given an positive integer n and a sequence a₁…a_n. There are q queries. Each query has one of two formats :

- Format 0 l r k : you need to output the k-th smallest positive integer that can’t be partition into a sum of any subsequence of a_l...a_r 

- Format 1 l r x : you need to output the numbers of ways to partition x into a sum of a subseqence of a_l...a_r (or the numbers of subsequence that sum of all its elements equal to x) (modulo 2³²)

Input :

-       Fist line : two positive n and q (1 ≤ n ≤ 100, 1 ≤ q ≤ 10000)

-       Second line : n positive a₁…a_n­ (0 ≤ a_i ≤ 100)

-       Next q lines : each line denotes a query with one of two format listed above (1 ≤ l ≤ r ≤ n, 1 ≤ k ≤ 10⁹, 0 ≤ x ≤ 10⁹)

Output :

-       q lines : the i-th line is the answer of i-th query.

Sample :

Input :

5 3

1 0 2 4 1

0 2 3 2

1 1 4 0

1 2 5 3

Output :

3

1

2