#1145601 (TypeScript) No.3433 [Cherry 8th Tune A] ADD OIL!

• 問題: No.3433 [Cherry 8th Tune A] ADD OIL!
• ユーザー: occhan
• 提出日時: 2026-01-23 22:09:39
• 言語: TypeScript (5.9.3)
• 結果: AC
• 実行時間: 187 ms / 2,000 ms
• コード長: 26,405 bytes
• コンパイル時間: 8,730 ms
• コンパイル使用メモリ: 319,116 KB
• 実行使用メモリ: 59,092 KB
• 最終ジャッジ日時: 2026-01-23 22:11:05
• 合計ジャッジ時間: 11,376 ms
• ジャッジサーバーID （参考情報）: judge2 / judge1

ファイルパターン	結果
other	AC * 12

ソースコード

// start

import { createInterface } from "readline";
import * as fs from "fs";

function main() {
  // ここに処理を記述して

  let T = nextNum();
  while (T--) {
    let [N,K] = nextNums(2);
    let A = nextBigInts(N);
    let ans = 10n**18n;
    for (let i = 0; i < N; i++) {
      let sum = 1n;
      for (let j = 0; j < N; j++) {
        if (i==j) {
          sum*=(A[j]-BigInt(K));
        } else {
          sum*= A[j];
        }
      }
      ans = bigIntMin(ans,sum);
    }
    if (T == 0) {
      print(ans);
    } else {
      println(ans);
    }
  }

  // 処理終了
}

declare global {
  interface Array<T> {
    last(): T | undefined
    isEmpty(): boolean
  }
}
Array.prototype.last = function () {
  return this.length === 0 ? undefined : this[this.length - 1]
}
Array.prototype.isEmpty = function () {
  return this.length === 0
}

const less = <T>(a: T, b: T) => (a == b ? 0 : a < b ? -1 : 1)
const greater = <T>(a: T, b: T) => (a == b ? 0 : a < b ? 1 : -1)
const bigIntMax = (...args: bigint[]) => args.reduce((m, e) => (e > m ? e : m))
const bigIntMin = (...args: bigint[]) => args.reduce((m, e) => (e < m ? e : m))
const bigIntAbs = (arg: bigint) => (arg < 0 ? -arg : arg)
const bigIntSqrt = (n) => {
  if (n == 0n) {
    return 0n;
  }
  let x = n;
  let y = (x + 1n) / 2n;
  while (x !== y) {
    x = y;
    y = (x + n / x) / 2n;
  }
  return x;
}

let inputs = "";
let inputArray: string[];
let currentIndex = 0;

let outputBuffer = "";

let yes = "Yes";
let no = "No";
let MOD998244353 = 998244353;

let dxy4 = [[-1,0],[0,1],[1,0],[0,-1]];
let dxy8 = [[-1,0],[-1,1],[0,1],[1,1],[1,0],[1,-1],[0,-1],[-1,-1]];

// // インタラクティブ用
// // お決まりのインプットはコメントアウト、main関数にasync、最後にrl.close()を忘れない
// // 詳しくはABC244-Cをチェック
// const rl = createInterface({
//   input: process.stdin,
//   output: process.stdout,
// });

// const input: string[] = [];
// rl.on("line", (line: string) => {
//   input.push(line);
// });

// const gl = async (): Promise<string> => {
//   while (!input.length) {
//     await new Promise((resolve) => setTimeout(resolve, 0));
//   }
//   return input.shift()!.trim();
// };

function next() {
  return inputArray[currentIndex++];
}
function nextNum() {
  return +next();
}
function nextBigInt() {
  return BigInt(next());
}
function nexts(length: number) {
  const arr: any[] = [];
  for(let i = 0; i < length; ++i) arr[i] = next();
  return arr;
}
function nextNums(length: number) {
  const arr: any[] = [];
  for(let i = 0; i < length; ++i) arr[i] = nextNum();
  return arr;
}
function nextBigInts(length: number) {
  const arr: any[] = [];
  for(let i = 0; i < length; ++i) arr[i] = nextBigInt();
  return arr;
}

function print(out: string | number | bigint): void;
function print<T>(out: Array<T>, separator: string): void;
function print<T>(out: string | number | bigint | Array<T>, separator?: string) {
  if (Array.isArray(out)) {
    outputBuffer += out.join(separator);
  } else {
    outputBuffer += out;
  }
}

function println(out: string | number | bigint): void;
function println<T>(out: Array<T>, separator: string): void;
function println<T>(out: string | number | bigint | Array<T>, separator?: string) {
  if (Array.isArray(out)) {
    print(out, separator || "");
  } else {
    print(out);
  }
  print("\n");
}

function flush() {
  console.log(outputBuffer);
}

function intDiv(a: number, b: number): number {
  return Math.trunc(a / b);
}

function lowerBound<T, U>(list: T[], value: U,
  less: (l: T, r: U) => boolean = (l: T, r: U) => l as any < r
): number {
  let count = list.length;
  let first = 0;
  while (0 < count) {
    const count2 = count / 2 | 0;
    const mid = first + count2;
    if (less(list[mid], value)) {
      first = mid + 1;
      count -= count2 + 1;
    } else {
      count = count2;
    }
  }
  return first;
}

function upperBound<T, U>(list: T[], value: U,
  less: (l: U, r: T) => boolean = (l: U, r: T) => l as any < r
): number {
  return lowerBound(list,value,(l,r)=>!less(r,l));
}

function nextPermutation(arr) {
  const len = arr.length;
  let left = len - 2;
  while (left >= 0 && arr[left] >= arr[left+1]){
    left--;
  }  
  if (left < 0){
    return false;
  }
  let right = len - 1;
  while (arr[left] >= arr[right]){
    right--;
  }
  const t = arr[left];
  arr[left] = arr[right]; 
  arr[right] = t; 
  left++;
  right = len - 1;
  while (left < right) {
    const t = arr[left]; 
    arr[left] = arr[right]; 
    arr[right] = t; 
    left++;
    right--;
  }
  return true;
}

function gcd(a: number, b: number): number;
function gcd(a: bigint, b: bigint): bigint;
function gcd(a: number | bigint, b: number | bigint): number | bigint {
  if (b == 0 || b ==BigInt(0)) {
    return a;
  }
  if (typeof a === 'number' && typeof b === 'number') {
    const r = a % b;
    return gcd(b, r);
  } else if (typeof a === 'bigint' && typeof b === 'bigint') {
    const r = a % b;
    return gcd(b, r);
  }
  return 0;
}


function lcm(a: bigint, b: bigint): bigint {
  try {
    return a/gcd(a,b)*b;
  } catch(e) {
    return -1n;
  }
}

function eratosthenesPrime(N = 10**6) {
  let b = Array<boolean>(N+1).fill(true);
  b[0]=false;
  b[1]=false;
  let prime = [2];
  for (let i = 4; i <= N; i+=2) {
    b[i] = false;
  }
  for (let i = 3; i <= N; i+=2) {
    if (b[i]) {
      prime.push(i);
      for (let j = i*3; j <= N; j+=i*2) {
        b[j] = false;
      }
    }
  }
  return prime;
}

function enumDiv(n) {
  let set = new Set<number>();
  for (let i = 1; i*i <= n; i++) {
    if (n%i == 0) {
      set.add(i);
      set.add(intDiv(n,i));
    }
  }
  return [...set];
}

// https://atcoder.jp/users/nanana1o
declare global {
  interface Number {
    add(a: number): number
    sub(a: number): number
    mul(a: number): number
    pow(n: number): number
    div(a: number): number
  }
}

function useModint(M: number) {
  Number.prototype.add = function (a: number) {
    const t = (+this + a) % M
    return t < 0 ? t + M : t
  }
  Number.prototype.sub = function (a: number) {
    const t = (+this - a) % M
    return t < 0 ? t + M : t
  }
  Number.prototype.mul = function (a: number) {
    const s = +this
    const t = s * a
    return t <= Number.MAX_SAFE_INTEGER
      ? t % M
      : ((((s >> 16) * a) % M) * 65536 + (s & 65535) * a) % M
  }
  Number.prototype.pow = function (n: number) {
    let x = +this
    if (x % M === 0) return 0
    let r = 1
    for (; n; x = x.mul(x), n >>>= 1) if (n & 1) r = r.mul(x)
    return r
  }
  Number.prototype.div = function (a: number) {
    return this.mul(a.pow(M - 2))
  }
}

function bigint_mod_pow(x: bigint, n: bigint, p: bigint) {
  if (x % p === 0n) return 0n
  let r = 1n
  for (x %= p; n; x = (x * x) % p, n >>= 1n) {
    if (n & 1n) r = (r * x) % p
  }
  return r
}

function z_algorithm(S) {
  let A = Array<number>(S.length).fill(0);
  A[0] = S.length;
  let i = 1, j = 0;
  while (i < S.length) {
    while (i+j < S.length && S[j] == S[i+j]) j++;
    A[i] = j;
    if (j == 0) {
      i++;
      continue;
    }
    let k = 1;
    while (i+k < S.length && k+A[k] < j) {
      A[i+k] = A[k];
      k++;
    }
    i += k;
    j -= k;
  }
  return A;
}

// 最長増加部分列（長さを返す）
function LIS(arr: number[]) {
  let dp: number[] = [];
  for (let num of arr) {
    let lb = lowerBound(dp,num);
    if (lb == dp.length) {
      dp.push(num);
    } else {
      dp[lb] = num;
    }
  }
  return dp.length;
}

function combinations<T>(arr: T[], k: number): T[][] {
  const result: T[][] = [];
  const combo: T[] = [];

  function dfs(start: number) {
    if (combo.length === k) {
      result.push([...combo]);
      return;
    }
    for (let i = start; i < arr.length; i++) {
      combo.push(arr[i]);
      dfs(i + 1);
      combo.pop();
    }
  }

  dfs(0);
  return result;
}

function builtin_popcount(n) {
  n |= 0; 
  let count = 0;
  while (n != 0) {
    n &= (n - 1); 
    count++;
  }
  return count;
}

class UnionFind {
  Parent: number[];
  constructor(edge: number) {
    this.Parent = Array<number>(edge).fill(-1);
  }
  root(node: number): number {
    if (this.Parent[node] < 0) return node;
    return this.Parent[node] = this.root(this.Parent[node]);
  }
  size(node: number): number {
    return -this.Parent[this.root(node)];
  }
  same(A: number, B: number): boolean {
    A = this.root(A);
    B = this.root(B);
    return A == B;
  }
  connect(A: number, B: number): boolean {
    A = this.root(A);
    B = this.root(B);
    if (A == B) {
      return false;
    }
    if (this.size(A) < this.size(B)) {
      let tmp = A;
      A = B;
      B = tmp;
    }
    this.Parent[A] += this.Parent[B];
    this.Parent[B] = A;
    return true;
  }
}

// aの優先度が高ければtrue
type Compare<T> = (a: T, b: T) => boolean;
class PriorityQueue<T> {
  private list = new Array<T>();
  constructor(private compare: Compare<T>) {}
  public push(v: T) {
    this.list.push(v);
    const back = this.list.length - 1;
    this.against(back);
  }
  private against(child: number) {
    if (child === 0) return;
    const parent = Math.ceil(child / 2) - 1;
    const childValue = this.list[child];
    const parentValue = this.list[parent];
    if (this.compare(childValue, parentValue)) {
      this.swap(child, parent);
      this.against(parent);
    }
  }
  private swap(a: number, b: number) {
    const tmp = this.list[a];
    this.list[a] = this.list[b];
    this.list[b] = tmp;
  }
  public top(): T {
    if (this.list.length === 0) throw new Error("empty");
    return this.list[0];
  }
  public pop(): T {
    if (this.list.length === 0) throw new Error("empty");
    if (this.list.length === 1) {
      const ans = this.top();
      this.list.pop();
      return ans;
    }
    const ans = this.top();
    this.list[0] = this.list.pop()!;
    this.flow(0);
    return ans;
  }
  private flow(parent: number) {
    const parentValue = this.list[parent];
    const left = parent * 2 + 1;
    const right = parent * 2 + 2;
    if (!this.inRange(left)) {
      return;
    }
    if (!this.inRange(right)) {
      // 左子はいるが右子はいない
      const leftValue = this.list[left];
      if (this.compare(leftValue, parentValue)) {
        this.swap(parent, left);
      }
      return;
    }
    const leftValue = this.list[left];
    const rightValue = this.list[right];
    const target = this.compare(leftValue, rightValue) ? left : right;
    const targetValue = this.list[target];
    if (this.compare(targetValue, parentValue)) {
      this.swap(parent, target);
      this.flow(target);
    }
  }
  private inRange(index: number): boolean {
    return index < this.list.length;
  }
  public size() {
    return this.list.length;
  }
}

// 01-bfsのときは無理にdequeを使わず、2つの配列を使う方が速い（ABC431-E）
class Deque<T> {
  private data: (T | undefined)[];
  private head: number;
  private tail: number;
  private capacity: number;
  constructor(capacity: number = 1 << 20) {
    this.capacity = capacity;
    this.data = new Array(capacity);
    this.head = capacity >> 1;
    this.tail = capacity >> 1;
  }
  push(value: T): void {
    this.data[this.tail++] = value;
  }
  unshift(value: T): void {
    this.data[--this.head] = value;
  }
  shift(): T | undefined {
    return this.head < this.tail ? this.data[this.head++] : undefined;
  }
  pop(): T | undefined {
    return this.head < this.tail ? this.data[--this.tail] : undefined;
  }
  peekHead(): T | undefined {
    return this.head < this.tail ? this.data[this.head] : undefined;
  }
  peekHeadIdx(idx: number): T | undefined {
    return this.head+idx < this.tail ? this.data[this.head+idx] : undefined;
  }
  peekTail(): T | undefined {
    return this.head < this.tail ? this.data[this.tail - 1] : undefined;
  }
  peekTailIdx(idx: number): T | undefined {
    return this.head < this.tail-idx ? this.data[this.tail-idx - 1] : undefined;
  }
  getLength(): number {
    return this.tail - this.head;
  }
}

// オイラーツアーのメモ
// let E;
// let L = Array.from({length: 101010},() => 0);
// let R = Array.from({length: 101010},() => 0);
// let idx = 0;
// function euler(cu, pa = -1) {
//     L[cu] = idx;
//     idx++;
//     for (let to of E[cu]) if (to != pa) euler(to, cu);
//     R[cu] = idx;
// }

// https://atcoder.jp/users/nanana1o
abstract class SegmentTree<T = number> {
  protected abstract getDefaultValue(): T
  protected abstract merger(v1: T, v2: T): T
  protected abstract updater(oldV: T, newV: T): T

  private n: number
  private readonly len: number
  private readonly tree: T[]

  constructor(lenOrArray: number | T[]) {
    this.len = typeof lenOrArray === 'number' ? lenOrArray : lenOrArray.length
    this.n = 1
    while (this.n < this.len) {
      this.n *= 2
    }

    const bufsize = this.n * 2
    this.tree = Array(bufsize)
    this.tree[0] = this.getDefaultValue()

    if (Array.isArray(lenOrArray)) {
      for (let i = 0; i < this.len; i++) this.tree[this.n + i] = lenOrArray[i]
      for (let i = this.len; i < this.n; i++) this.tree[this.n + i] = this.getDefaultValue()
      for (let i = this.n - 1; i >= 1; i--)
        this.tree[i] = this.merger(this.tree[i * 2], this.tree[i * 2 + 1])
    } else {
      for (let i = 1; i < bufsize; i++) this.tree[i] = this.getDefaultValue()
    }
  }

  get length() {
    return this.len
  }

  update(index: number, value: T): void {
    let k = index + this.n
    this.tree[k] = this.updater(this.tree[k], value)
    while (k > 1) {
      k >>= 1
      this.tree[k] = this.merger(this.tree[2 * k], this.tree[2 * k + 1])
    }
  }

  get(left: number, right: number): T {
    let res: T = this.getDefaultValue()
    for (left += this.n, right += this.n; left < right; left >>= 1, right >>= 1) {
      if (left & 1) {
        res = this.merger(res, this.tree[left++])
      }

      if (right & 1) {
        res = this.merger(res, this.tree[--right])
      }
    }

    return res
  }
}

class MaxSegmentTree2 extends SegmentTree<number> {
  protected getDefaultValue() {
    return -Infinity
  }

  protected merger(a: number, b: number) {
    return Math.max(a, b)
  }

  protected updater(oldV: number, newV: number) {
    return newV
  }
}

class MinSegmentTree2 extends SegmentTree<number> {
  protected getDefaultValue() {
    return Infinity
  }

  protected merger(a: number, b: number) {
    return Math.min(a, b)
  }

  protected updater(oldV: number, newV: number) {
    return newV
  }
}

class SumSegmentTree2 extends SegmentTree<number> {
  protected getDefaultValue() {
    return 0
  }

  protected merger(a: number, b: number) {
    return a+b
  }

  protected updater(oldV: number, newV: number) {
    return newV
  }
}

class XorSegmentTree2 extends SegmentTree<number> {
  protected getDefaultValue() {
    return 0
  }

  protected merger(a: number, b: number) {
    return a^b
  }

  protected updater(oldV: number, newV: number) {
    return oldV^newV
  }
}

class ArraySegmentTree2 extends SegmentTree<number[]> {
  protected getDefaultValue() {
    return [];
  }

  protected merger(a: number[], b: number[]) {
    return a[0] > b[0] ? a : b;
  }

  protected updater(oldV: number[], newV: number[]) {
    return newV;
  }
}

class LazySegmentTree {
  private size: number;
  private tree: number[];
  private lazy: number[];
  constructor(size: number) {
    this.size = 1;
    while (this.size < size) {
      this.size *= 2;
    }
    this.tree = Array(2 * this.size - 1).fill(0);
    this.lazy = Array(2 * this.size - 1).fill(0);
  }
  query(left: number, right: number): number {
    return this.querySub(left, right, 0, 0, this.size);
  }
  update(left: number, right: number, value: number): void {
    this.updateSub(left, right, value, 0, 0, this.size);
  }
  private querySub(
    queryLeft: number,
    queryRight: number,
    index: number,
    nodeLeft: number,
    nodeRight: number
  ): number {
    if (nodeRight <= queryLeft || queryRight <= nodeLeft) {
      return 0;
    }
    this.applyLazyUpdate(index);
    if (queryLeft <= nodeLeft && nodeRight <= queryRight) {
      return this.tree[index];
    }
    const mid = Math.floor((nodeLeft + nodeRight) / 2);
    const leftValue = this.querySub(queryLeft, queryRight, index * 2 + 1, nodeLeft, mid);
    const rightValue = this.querySub(queryLeft, queryRight, index * 2 + 2, mid, nodeRight);
    return Math.max(leftValue, rightValue);
  }
  private updateSub(
    queryLeft: number,
    queryRight: number,
    value: number,
    index: number,
    nodeLeft: number,
    nodeRight: number
  ): void {
    if (nodeRight <= queryLeft || queryRight <= nodeLeft) {
      return;
    }
    if (queryLeft <= nodeLeft && nodeRight <= queryRight) {
      this.lazy[index] = value;
      this.applyLazyUpdate(index);
      return;
    }
    const mid = Math.floor((nodeLeft + nodeRight) / 2);
    this.updateSub(queryLeft, queryRight, value, index * 2 + 1, nodeLeft, mid);
    this.updateSub(queryLeft, queryRight, value, index * 2 + 2, mid, nodeRight);
    this.tree[index] = Math.max(this.tree[index * 2 + 1], this.tree[index * 2 + 2]);
  }
  private applyLazyUpdate(index: number): void {
    if (this.lazy[index] === 0) {
      return;
    }
    this.tree[index] = this.lazy[index];
    if (index < this.size - 1) {
      this.lazy[index * 2 + 1] = this.lazy[index];
      this.lazy[index * 2 + 2] = this.lazy[index];
    }
    this.lazy[index] = 0;
  }
}

class Trie {
  next: Map<number, Trie> = new Map();
  nextSet: TreeMultiSet<number> = new TreeMultiSet();
  idx: number[] = [];
}

// https://atcoder.jp/users/mst40
class TreeSetNode<T> {
  value: T;
  left: TreeSetNode<T> | null;
  right: TreeSetNode<T> | null;
  height: number;
  count: number;
  constructor(n: T) {
    this.value = n;
    this.left = null;
    this.right = null;
    this.height = 1;
    this.count = 1;
  }
  incCnt() {
    this.count++;
  }
  decCnt() {
    this.count--;
  }
}
class TreeMultiSet<T> {
  root: TreeSetNode<T> | null;
  constructor() {
    this.root = null;
  }

  add(val: T) {
    this.root = this._addHelper(this.root, val);
  }
  delete(val: T): boolean {
    const newTree = this._deleteHelper(this.root, val);
    this.root = newTree;
    if (!newTree) {
      return false;
    }
    return true;
  }
  count(value: T): number {
    return this._getCountHelper(this.root, value);
  }
  min(): T | undefined {
    if (!this.root) {
      return undefined;
    }
    return this._findMin(this.root!).value;
  }
  max() {
    if (!this.root) {
      return undefined;
    }
    return this._findMax(this.root!).value;
  }
  lower_bound(val: T) {
    return this._lower_boundHelper(this.root, val);
  }
  upper_bound(val: T) {
    return this._upper_boundHelper(this.root, val);
  }
  prev(val: T): T | undefined {
    return this._prevHelper(this.root, val);
  }

  next(val: T): T | undefined {
    return this._nextHelper(this.root, val);
  }

  /** private */
  private _addHelper(node: TreeSetNode<T> | null, val: T): TreeSetNode<T> {
    if (!node) {
      return new TreeSetNode(val);
    }
    if (val < node.value) {
      node.left = this._addHelper(node.left, val);
    } else if (node.value < val) {
      node.right = this._addHelper(node.right, val);
    } else {
      node.incCnt();
      return node;
    }

    node.height = this._newHeight(node);
    return this._balancing(node, val);
  }

  private _getBalanceFactor(node: TreeSetNode<T>): number {
    return this._getHeight(node.right) - this._getHeight(node.left);
  }
  private _getHeight(node: TreeSetNode<T> | null): number {
    return node ? node.height : 0;
  }
  private _newHeight(node: TreeSetNode<T>): number {
    return Math.max(this._getHeight(node.left), this._getHeight(node.right)) + 1;
  }
  private _balancing(node: TreeSetNode<T>, val: T) {
    const factor = this._getBalanceFactor(node);
    if (factor < -1) {
      if (val < node.left!.value) {
        return this._rightRotate(node);
      } else {
        node.left = this._leftRotate(node.left!);
        return this._rightRotate(node);
      }
    } else if (1 < factor) {
      if (val > node.right!.value) {
        return this._leftRotate(node);
      } else {
        node.right = this._rightRotate(node.right!);
        return this._leftRotate(node);
      }
    }

    return node;
  }
  private _leftRotate(node: TreeSetNode<T>) {
    const pivot = node.right!;
    node.right = pivot ? pivot.left : null;
    if (pivot) pivot.left = node;

    node.height = this._newHeight(node);
    if (pivot) pivot.height = this._newHeight(pivot);

    return pivot || node;
  }

  private _rightRotate(node: TreeSetNode<T>) {
    const pivot = node.left!;
    node.left = pivot ? pivot.right : null;
    if (pivot) pivot.right = node;

    node.height = this._newHeight(node);
    if (pivot) pivot.height = this._newHeight(pivot);

    return pivot || node;
  }
  private _getCountHelper(node: TreeSetNode<T> | null, value: T): number {
    // value is not exsists.
    if (!node) {
      return 0;
    }
    // binary search(recursive)
    if (value < node.value) {
      return this._getCountHelper(node.left, value);
    } else if (value > node.value) {
      return this._getCountHelper(node.right, value);
    } else {
      return node.count;
    }
  }
  private _deleteHelper(node: TreeSetNode<T> | null, val: T): TreeSetNode<T> | null {
    if (!node) {
      return null;
    }
    if (val < node.value) {
      node.left = this._deleteHelper(node.left, val);
    } else if (val > node.value) {
      node.right = this._deleteHelper(node.right, val);
    } else {
      if (1 < node.count) {
        node.decCnt();
        return node;
      }
      if (!node.left) {
        node = node.right;
      } else if (!node.right) {
        node = node.left;
      } else {
        const min = this._findMin(node.right);
        node.value = min.value;
        node.right = this._deleteHelper(node.right, min.value);
      }

      if (node) {
        node.height = this._newHeight(node);
        return this._balancing(node, val);
      }
    }
    return node;
  }
  private _findMin(node: TreeSetNode<T>): TreeSetNode<T> {
    let curr = node;
    while (curr.left) {
      curr = curr.left;
    }
    return curr;
  }
  private _findMax(node: TreeSetNode<T>): TreeSetNode<T> {
    let curr = node;
    while (curr.right) {
      curr = curr.right;
    }
    return curr;
  }
  private _lower_boundHelper(node: TreeSetNode<T> | null, val: T): T | undefined {
    if (!node) {
      return undefined;
    }

    if (val <= node.value) {
      const left = this._lower_boundHelper(node.left, val);
      return left !== undefined ? left : node.value;
    } else {
      return this._lower_boundHelper(node.right, val);
    }
  }
  private _upper_boundHelper(node: TreeSetNode<T> | null, val: T): T | undefined {
    if (!node) {
      return undefined;
    }

    if (val < node.value) {
      const left = this._upper_boundHelper(node.left, val);
      return left !== undefined ? left : node.value;
    } else {
      return this._upper_boundHelper(node.right, val);
    }
  }
  private _prevHelper(node: TreeSetNode<T> | null, val: T): T | undefined {
    if (!node) {
      return undefined;
    }

    if (val <= node.value) {
      return this._prevHelper(node.left, val);
    } else {
      const right = this._prevHelper(node.right, val);
      return right !== undefined ? right : node.value;
    }
  }

  private _nextHelper(node: TreeSetNode<T> | null, val: T): T | undefined {
    if (!node) {
      return undefined;
    }

    if (val >= node.value) {
      return this._nextHelper(node.right, val);
    } else {
      const left = this._nextHelper(node.left, val);
      return left !== undefined ? left : node.value;
    }
  }
}

class FenwickTree {
  arraySize;
  treeArray;
  constructor(arraySize) {
    this.arraySize = arraySize;
    // Fill tree array with zeros.
    this.treeArray = Array(this.arraySize + 1).fill(0);
  }

  increase(position, value) {
    if (position < 0 || position > this.arraySize) {
      throw new Error('Position is out of allowed range');
    }
    for (let i = position; i <= this.arraySize; i += (i & -i)) {
      this.treeArray[i] += value;
    }
    return this;
  }

  query(position) {
    if (position < 0 || position > this.arraySize) {
      throw new Error('Position is out of allowed range');
    }
    let sum = 0;
    for (let i = position; i >= 0; i -= (i & -i)) {
      sum += this.treeArray[i];
    }
    return sum;
  }

  queryRange(leftIndex, rightIndex) {
    if (leftIndex > rightIndex) {
      throw new Error('Left index can not be greater than right one');
    }
    if (leftIndex === 0) {
      return this.query(rightIndex);
    }
    return this.query(rightIndex) - this.query(leftIndex - 1);
  }
}

class FenwickTreeMod {
  arraySize;
  treeArray;
  constructor(arraySize) {
    this.arraySize = arraySize;
    // Fill tree array with zeros.
    this.treeArray = Array(this.arraySize + 1).fill(0);
  }

  increase(position, value) {
    if (position < 0 || position > this.arraySize) {
      throw new Error('Position is out of allowed range');
    }
    for (let i = position; i <= this.arraySize; i += (i & -i)) {
      this.treeArray[i] = this.treeArray[i].add(value);
    }
    return this;
  }

  query(position) {
    if (position < 0 || position > this.arraySize) {
      throw new Error('Position is out of allowed range');
    }
    let sum = 0;
    for (let i = position; i >= 0; i -= (i & -i)) {
      sum = sum.add(this.treeArray[i]);
    }
    return sum;
  }

  queryRange(leftIndex, rightIndex) {
    if (leftIndex > rightIndex) {
      throw new Error('Left index can not be greater than right one');
    }
    if (leftIndex === 0) {
      return this.query(rightIndex);
    }
    return this.query(rightIndex).sub(this.query(leftIndex - 1));
  }
}

// end

// デバッグ環境がWindowsであれば条件分岐する
if (process.env.OS == "Windows_NT") {
  const stream = createInterface({
    input: process.stdin,
    output: process.stdout,
  });
  stream.on("line", (line) => {
    inputs += line;
    inputs += "\n";
  });
  stream.on("close", () => {
    inputArray = inputs.split(/\s/);
    main();
    flush();
  });
} else {
  inputs = fs.readFileSync("/dev/stdin", "utf8");
  inputArray = inputs.split(/\s/);
  main();
  flush();
}