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

• First 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