BLSUMSEQ - Sum of subsequences

Given an positive integer n and a sequence a1 ... an. 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 al ... ar.
  • Format 1 l r x: you need to output the numbers of ways to partition x into a sum of a subseqence of al ... ar (or the numbers of subsequence that sum of all its elements equal to x) (modulo 232).

Input

  • First line: two positive n and q (1 ≤ n ≤ 100, 1 ≤ q ≤ 10000)
  • Second line: n positive a1…an­ (0 ≤ ai ≤ 100)
  • Next q lines: each line denotes a query with one of two format listed above (1 ≤ l ≤ r ≤ n, 1 ≤ k ≤ 109, 0 ≤ x ≤ 109)

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

Được gửi lên bởi:Kata
Ngày:2014-03-12
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:Own problem

hide comments
2014-10-09 12:51:30 Mew.
Cho mình hỏi với truy vấn 1, 1 số có thể được sử dụng nhiều lần hay không ?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.