import pypyjit pypyjit.set_param( "threshold=1," "function_threshold=1," "trace_eagerness=1," "decay=0" ) WORD_BITS = 63 WORD_MASK = (1 << WORD_BITS) - 1 _LOW_KEEP = [0] * WORD_BITS _LOW_BITS = [0] * WORD_BITS for _r in range(1, WORD_BITS): _LOW_KEEP[_r] = (1 << (WORD_BITS - _r)) - 1 _LOW_BITS[_r] = (1 << _r) - 1 class BitSet: __slots__ = ("nbits", "nwords", "_last_mask", "_words", "_lo", "_hi") def __init__(self, nbits, value=0): if nbits <= 0: raise ValueError("nbits must be positive") if value < 0: raise ValueError("value must be non-negative") self.nbits = nbits nwords = (nbits + WORD_BITS - 1) // WORD_BITS self.nwords = nwords rem = nbits - (nwords - 1) * WORD_BITS self._last_mask = WORD_MASK if rem == WORD_BITS else (1 << rem) - 1 words = [0] * (nwords + 1) i = 0 while i < nwords and value: words[i] = value & WORD_MASK value >>= WORD_BITS i += 1 words[nwords - 1] &= self._last_mask self._words = words hi = min(i - 1, nwords - 1) while hi >= 0 and words[hi] == 0: hi -= 1 if hi < 0: self._lo = nwords self._hi = -1 else: lo = 0 while words[lo] == 0: lo += 1 self._lo = lo self._hi = hi def _clean_for_right_shift(self): words = self._words words[self.nwords - 1] &= self._last_mask words[self.nwords] = 0 def _check_compatible(self, other): if not isinstance(other, BitSet): raise TypeError("operand must be BitSet") if self.nbits != other.nbits: raise ValueError("bitset sizes differ") def _trim(self): lo = self._lo hi = self._hi if hi < lo: self._lo = self.nwords self._hi = -1 return words = self._words last = self.nwords - 1 if hi > last: hi = last if hi == last: words[last] &= self._last_mask while lo <= hi and words[lo] == 0: lo += 1 while hi >= lo and words[hi] == 0: hi -= 1 if lo > hi: self._lo = self.nwords self._hi = -1 else: self._lo = lo self._hi = hi def copy(self): obj = object.__new__(BitSet) obj.nbits = self.nbits obj.nwords = self.nwords obj._last_mask = self._last_mask obj._words = self._words[:] obj._lo = self._lo obj._hi = self._hi return obj def clear(self): self._words = [0] * (self.nwords + 1) self._lo = self.nwords self._hi = -1 return self def set_all(self): n = self.nwords words = [WORD_MASK] * (n + 1) words[n - 1] = self._last_mask words[n] = 0 self._words = words self._lo = 0 self._hi = n - 1 return self def flip_all(self): words = self._words n = self.nwords i = 0 while i < n - 1: words[i] = WORD_MASK ^ words[i] i += 1 last = n - 1 words[last] = self._last_mask ^ (words[last] & self._last_mask) words[n] = 0 self._lo = 0 self._hi = last self._trim() return self def set(self, i): if i < 0 or i >= self.nbits: raise IndexError(i) q = i // WORD_BITS r = i - q * WORD_BITS self._words[q] |= 1 << r if q < self._lo: self._lo = q if q > self._hi: self._hi = q return self def reset(self, i): if i < 0 or i >= self.nbits: raise IndexError(i) q = i // WORD_BITS r = i - q * WORD_BITS self._words[q] &= WORD_MASK ^ (1 << r) return self def flip(self, i): if i < 0 or i >= self.nbits: raise IndexError(i) q = i // WORD_BITS r = i - q * WORD_BITS self._words[q] ^= 1 << r if self._words[q]: if q < self._lo: self._lo = q if q > self._hi: self._hi = q return self def test(self, i): if i < 0 or i >= self.nbits: raise IndexError(i) q = i // WORD_BITS r = i - q * WORD_BITS return ((self._words[q] >> r) & 1) != 0 def __getitem__(self, i): return self.test(i) def __setitem__(self, i, value): if i < 0 or i >= self.nbits: raise IndexError(i) q = i // WORD_BITS r = i - q * WORD_BITS bit = 1 << r if value: self._words[q] |= bit if q < self._lo: self._lo = q if q > self._hi: self._hi = q else: self._words[q] &= WORD_MASK ^ bit def count(self): if self._hi < self._lo: return 0 words = self._words lo = self._lo hi = self._hi last = self.nwords - 1 res = 0 i = lo while i <= hi: x = words[i] if i == last: x &= self._last_mask res += x.bit_count() i += 1 return res def any(self): if self._hi < self._lo: return False words = self._words i = self._lo hi = self._hi last = self.nwords - 1 while i <= hi: x = words[i] if i == last: x &= self._last_mask if x: if i > self._lo: self._lo = i return True i += 1 self._lo = self.nwords self._hi = -1 return False def none(self): return not self.any() def all(self): last = self.nwords - 1 if self._lo > 0 or self._hi < last: return False words = self._words i = 0 while i < last: if words[i] != WORD_MASK: return False i += 1 return (words[last] & self._last_mask) == self._last_mask def find_first(self): if self._hi < self._lo: return -1 words = self._words i = self._lo hi = self._hi last = self.nwords - 1 while i <= hi: x = words[i] if i == last: x &= self._last_mask if x: self._lo = i return i * WORD_BITS + (x & -x).bit_length() - 1 i += 1 self._lo = self.nwords self._hi = -1 return -1 def find_next(self, i): p = i + 1 if p < 0: p = 0 if p >= self.nbits or self._hi < self._lo: return -1 q = p // WORD_BITS r = p - q * WORD_BITS if q < self._lo: q = self._lo r = 0 hi = self._hi if q > hi: return -1 words = self._words last = self.nwords - 1 x = words[q] if q == last: x &= self._last_mask x >>= r if x: return q * WORD_BITS + r + (x & -x).bit_length() - 1 q += 1 while q <= hi: x = words[q] if q == last: x &= self._last_mask if x: return q * WORD_BITS + (x & -x).bit_length() - 1 q += 1 return -1 def find_last(self): if self._hi < self._lo: return -1 words = self._words i = self._hi lo = self._lo last = self.nwords - 1 while i >= lo: x = words[i] if i == last: x &= self._last_mask if x: self._hi = i return i * WORD_BITS + x.bit_length() - 1 i -= 1 self._lo = self.nwords self._hi = -1 return -1 def __iter__(self): if self._hi < self._lo: return words = self._words wi = self._lo hi = self._hi last = self.nwords - 1 while wi <= hi: x = words[wi] if wi == last: x &= self._last_mask base = wi * WORD_BITS while x: lsb = x & -x yield base + lsb.bit_length() - 1 x ^= lsb wi += 1 def ior_lshift(self, shift): """self |= self << shift""" if shift < 0: raise ValueError("negative shift count") if shift == 0 or shift >= self.nbits or self._hi < self._lo: return self words = self._words lo = self._lo hi = self._hi q = shift // WORD_BITS r = shift - q * WORD_BITS src = (self.nbits - 1 - shift) // WORD_BITS if src > hi: src = hi if src < lo: return self if r == 0: s = src while s >= lo: words[s + q] |= words[s] s -= 1 dh = src + q else: low_keep = _LOW_KEEP[r] rr = WORD_BITS - r s = src while s >= lo: x = words[s] dst = s + q words[dst] |= (x & low_keep) << r words[dst + 1] |= x >> rr s -= 1 dh = src + q + 1 if dh >= self.nwords: dh = self.nwords - 1 if dh > self._hi: self._hi = dh return self or_shift_left = ior_lshift def ior_rshift(self, shift): """self |= self >> shift""" if shift < 0: raise ValueError("negative shift count") if shift == 0 or shift >= self.nbits or self._hi < self._lo: return self self._clean_for_right_shift() words = self._words lo = self._lo hi = self._hi q = shift // WORD_BITS r = shift - q * WORD_BITS dhi = hi - q if dhi < 0: return self dlo = lo - q - (1 if r else 0) if dlo < 0: dlo = 0 limit = self.nwords - q - 1 if dhi > limit: dhi = limit if dlo > dhi: return self if r == 0: dst = dlo while dst <= dhi: words[dst] |= words[dst + q] dst += 1 else: low_bits = _LOW_BITS[r] rr = WORD_BITS - r last = self.nwords - 1 dst = dlo while dst <= dhi: src = dst + q x = words[src] >> r if src < last: x |= (words[src + 1] & low_bits) << rr words[dst] |= x dst += 1 if dlo < self._lo: self._lo = dlo return self or_shift_right = ior_rshift def ixor_lshift(self, shift): """self ^= self << shift""" if shift < 0: raise ValueError("negative shift count") if shift == 0: return self.clear() if shift >= self.nbits or self._hi < self._lo: return self words = self._words lo = self._lo hi = self._hi q = shift // WORD_BITS r = shift - q * WORD_BITS src = (self.nbits - 1 - shift) // WORD_BITS if src > hi: src = hi if src < lo: return self if r == 0: s = src while s >= lo: words[s + q] ^= words[s] s -= 1 dl = lo + q dh = src + q else: low_keep = _LOW_KEEP[r] rr = WORD_BITS - r s = src while s >= lo: x = words[s] dst = s + q words[dst] ^= (x & low_keep) << r words[dst + 1] ^= x >> rr s -= 1 dl = lo + q dh = src + q + 1 if dh >= self.nwords: dh = self.nwords - 1 if dl < self._lo: self._lo = dl if dh > self._hi: self._hi = dh return self xor_shift_left = ixor_lshift def ixor_rshift(self, shift): """self ^= self >> shift""" if shift < 0: raise ValueError("negative shift count") if shift == 0: return self.clear() if shift >= self.nbits or self._hi < self._lo: return self self._clean_for_right_shift() words = self._words lo = self._lo hi = self._hi q = shift // WORD_BITS r = shift - q * WORD_BITS dhi = hi - q if dhi < 0: return self dlo = lo - q - (1 if r else 0) if dlo < 0: dlo = 0 limit = self.nwords - q - 1 if dhi > limit: dhi = limit if dlo > dhi: return self if r == 0: dst = dlo while dst <= dhi: words[dst] ^= words[dst + q] dst += 1 else: low_bits = _LOW_BITS[r] rr = WORD_BITS - r last = self.nwords - 1 dst = dlo while dst <= dhi: src = dst + q x = words[src] >> r if src < last: x |= (words[src + 1] & low_bits) << rr words[dst] ^= x dst += 1 if dlo < self._lo: self._lo = dlo return self xor_shift_right = ixor_rshift def iand_lshift(self, shift): """self &= self << shift""" if shift < 0: raise ValueError("negative shift count") if shift == 0: return self if shift >= self.nbits or self._hi < self._lo: return self.clear() words = self._words lo = self._lo hi = self._hi q = shift // WORD_BITS r = shift - q * WORD_BITS dlo = lo + q if dlo > hi: return self.clear() dst = hi if r == 0: while dst >= dlo: words[dst] &= words[dst - q] dst -= 1 else: low_keep = _LOW_KEEP[r] rr = WORD_BITS - r while dst >= dlo: src = dst - q x = (words[src] & low_keep) << r if src > 0: x |= words[src - 1] >> rr words[dst] &= x dst -= 1 dst = lo while dst < dlo: words[dst] = 0 dst += 1 self._lo = dlo self._hi = hi self._trim() return self and_shift_left = iand_lshift def iand_rshift(self, shift): """self &= self >> shift""" if shift < 0: raise ValueError("negative shift count") if shift == 0: return self if shift >= self.nbits or self._hi < self._lo: return self.clear() self._clean_for_right_shift() words = self._words lo = self._lo hi = self._hi q = shift // WORD_BITS r = shift - q * WORD_BITS dhi = hi - q if dhi < lo: return self.clear() dst = lo if r == 0: while dst <= dhi: words[dst] &= words[dst + q] dst += 1 else: low_bits = _LOW_BITS[r] rr = WORD_BITS - r last = self.nwords - 1 while dst <= dhi: src = dst + q x = words[src] >> r if src < last: x |= (words[src + 1] & low_bits) << rr words[dst] &= x dst += 1 dst = dhi + 1 while dst <= hi: words[dst] = 0 dst += 1 self._lo = lo self._hi = dhi self._trim() return self and_shift_right = iand_rshift def __ilshift__(self, shift): if shift < 0: raise ValueError("negative shift count") if shift == 0: return self if shift >= self.nbits or self._hi < self._lo: return self.clear() words = self._words lo = self._lo hi = self._hi q = shift // WORD_BITS r = shift - q * WORD_BITS dlo = lo + q if dlo >= self.nwords: return self.clear() dhi = hi + q + (1 if r else 0) if dhi >= self.nwords: dhi = self.nwords - 1 dst = dhi if r == 0: while dst >= dlo: src = dst - q words[dst] = words[src] if src <= hi else 0 dst -= 1 else: low_keep = _LOW_KEEP[r] rr = WORD_BITS - r while dst >= dlo: src = dst - q x = 0 if src <= hi: x = (words[src] & low_keep) << r if src > lo: x |= words[src - 1] >> rr words[dst] = x dst -= 1 dst = lo while dst < dlo: words[dst] = 0 dst += 1 words[self.nwords] = 0 self._lo = dlo self._hi = dhi self._trim() return self def __irshift__(self, shift): if shift < 0: raise ValueError("negative shift count") if shift == 0: return self if shift >= self.nbits or self._hi < self._lo: return self.clear() self._clean_for_right_shift() words = self._words lo = self._lo hi = self._hi q = shift // WORD_BITS r = shift - q * WORD_BITS dhi = hi - q if dhi < 0: return self.clear() dlo = lo - q - (1 if r else 0) if dlo < 0: dlo = 0 dst = dlo if r == 0: while dst <= dhi: src = dst + q words[dst] = words[src] if src >= lo else 0 dst += 1 else: low_bits = _LOW_BITS[r] rr = WORD_BITS - r while dst <= dhi: src = dst + q x = 0 if src >= lo: x = words[src] >> r if src < hi: x |= (words[src + 1] & low_bits) << rr words[dst] = x dst += 1 dst = dhi + 1 while dst <= hi: words[dst] = 0 dst += 1 words[self.nwords] = 0 self._lo = dlo self._hi = dhi self._trim() return self def __lshift__(self, shift): res = self.copy() res <<= shift return res def __rshift__(self, shift): res = self.copy() res >>= shift return res def __ior__(self, other): self._check_compatible(other) if other._hi < other._lo: return self a = self._words b = other._words lo = other._lo hi = other._hi i = lo while i <= hi: a[i] |= b[i] i += 1 if lo < self._lo: self._lo = lo if hi > self._hi: self._hi = hi return self def __iand__(self, other): self._check_compatible(other) if self is other: return self if self._hi < self._lo or other._hi < other._lo: return self.clear() old_lo = self._lo old_hi = self._hi lo = max(old_lo, other._lo) hi = min(old_hi, other._hi) if lo > hi: return self.clear() a = self._words b = other._words i = old_lo while i < lo: a[i] = 0 i += 1 i = lo while i <= hi: a[i] &= b[i] i += 1 i = hi + 1 while i <= old_hi: a[i] = 0 i += 1 self._lo = lo self._hi = hi self._trim() return self def __ixor__(self, other): self._check_compatible(other) if self is other: return self.clear() if other._hi < other._lo: return self old_lo = self._lo old_hi = self._hi lo = other._lo hi = other._hi overlap = not (old_hi < lo or hi < old_lo) a = self._words b = other._words i = lo while i <= hi: a[i] ^= b[i] i += 1 if lo < self._lo: self._lo = lo if hi > self._hi: self._hi = hi if overlap: self._trim() return self def __or__(self, other): if not isinstance(other, BitSet): return NotImplemented res = self.copy() res |= other return res def __and__(self, other): if not isinstance(other, BitSet): return NotImplemented res = self.copy() res &= other return res def __xor__(self, other): if not isinstance(other, BitSet): return NotImplemented res = self.copy() res ^= other return res def __invert__(self): res = self.copy() res.flip_all() return res def intersects(self, other): self._check_compatible(other) lo = max(self._lo, other._lo) hi = min(self._hi, other._hi) if lo > hi: return False a = self._words b = other._words last = self.nwords - 1 i = lo while i <= hi: x = a[i] & b[i] if i == last: x &= self._last_mask if x: return True i += 1 return False def is_subset_of(self, other): self._check_compatible(other) if self._hi < self._lo: return True a = self._words b = other._words i = self._lo hi = self._hi last = self.nwords - 1 while i <= hi: x = a[i] y = b[i] if other._lo <= i <= other._hi else 0 if i == last: x &= self._last_mask y &= self._last_mask if x & (WORD_MASK ^ y): return False i += 1 return True def to_int(self): words = self._words i = self._hi if i < self._lo: return 0 value = words[i] if i == self.nwords - 1: value &= self._last_mask i -= 1 while i >= 0: value = (value << WORD_BITS) | words[i] i -= 1 return value def __len__(self): return self.nbits def __bool__(self): return self.any() def __eq__(self, other): if not isinstance(other, BitSet) or self.nbits != other.nbits: return False lo = min(self._lo, other._lo) hi = max(self._hi, other._hi) if hi < lo: return True a = self._words b = other._words last = self.nwords - 1 i = lo while i <= hi: x = a[i] y = b[i] if i == last: mask = self._last_mask x &= mask y &= mask if x != y: return False i += 1 return True import sys def solve(): N, S = map(int, sys.stdin.readline().split()) A = list(map(int, sys.stdin.readline().split())) C = BitSet(S + 1) C.set(0) for i in A: C|=C<