import sys input = sys.stdin.readline #先頭からのsum,addをO(logN) class Fenwick_Tree: def __init__(self, n): self._n = n # 要素数 self.data = [0] * n self.depth = n.bit_length() def add(self, p, x): assert 0 <= p < self._n p += 1 # 0-indexed -> 1-indexed while p <= self._n: self.data[p - 1] += x # dataを更新 p += p & -p # pにLSB(p)を加算,data[i]の長さを示す def _sum(self, r):#s = a0+a1+...+a[r-1] or 0 s = 0 # 総和を入れる変数 while r > 0: s += self.data[r - 1] r -= r & -r # rからLSB(r)を減算 return s def sum(self, l, r):#[l,r)の総和 assert 0 <= l <= r <= self._n return self._sum(r) - self._sum(l) def bisect_l(self,x): #wa >= xとなる最小のidx pos = 0 ; wa = 0 for i in range(self.depth,-1,-1): k = pos + (1<= xとなる最大のidx if x < 0 : return 0 pos = 0 ; wa = 0 for i in range(self.depth,-1,-1): k = pos + (1 << i) if k < self._n and wa + self.data[k-1] <= x: wa += self.data[k-1] pos += (1<= k : continue ans[x] = lrch[idx][2] print(*ans,sep="\n")