Given two sequences of integers a and b of the same length n and an integer S. There are Q queries belonging to a in the following two forms: • 1 i x y: Assign ai = x, bi = y • 2 H: Need to find 1 ≤ L ≤ H such that aL + aL+1 + . . . + aH ≥ S and bL + bL+1 + . . . + bH has the smallest possible value Data • The first line contains two integers n, S (1 n ≤ 10^5 , −10^18 ≤ S ≤ 10^18). • The second line contains n integers a1, a2, . . . , an (−10^9 ai 10^9) • The third line contains n integers b1, b2, . . . , bn (−10^9 bi ≤ 10^9) • The fourth line contains the positive integer Q (1 ≤ Q ≤ 10^5) • Next Q lines, each with one query: 1 i x y (1 ≤ i ≤ n; −10^9 ≤ x, y ≤ 10^9) or 2 H (1 ≤ H ≤ n)