//////////////////////////////////////////////Template/////////////////////////////////////////////////////////////
function Bisect() {
 return { insort_right, insort_left, bisect_left, bisect_right }
 function insort_right(a, x, lo = 0, hi = null) {
 lo = bisect_right(a, x, lo, hi)
 a.splice(lo, 0, x)
 }
 function bisect_right(a, x, lo = 0, hi = null) {
 // > upper_bound
 if (lo < 0) throw new Error('lo must be non-negative')
 if (hi == null) hi = a.length
 while (lo < hi) {
 let mid = parseInt((lo + hi) / 2)
 x < a[mid] ? (hi = mid) : (lo = mid + 1)
 }
 return lo
 }
 function insort_left(a, x, lo = 0, hi = null) {
 lo = bisect_left(a, x, lo, hi)
 a.splice(lo, 0, x)
 }
 function bisect_left(a, x, lo = 0, hi = null) {
 // >= lower_bound
 if (lo < 0) throw new Error('lo must be non-negative')
 if (hi == null) hi = a.length
 while (lo < hi) {
 let mid = parseInt((lo + hi) / 2)
 a[mid] < x ? (lo = mid + 1) : (hi = mid)
 }
 return lo
 }
}

const LIS = arr => {
 const n = arr.length
 // memo[j]: 长度为j的最长自增子序列最后一位的index(同长度最后一位最小). 
 // stores the index k of the smallest value X[k] such that there is an increasing subsequence of length j ending at X[k] on the range k ≤ i
 // pre[k]: 以arr[k]结尾的LIS,arr[k]之前一个元素的index. 
 // stores the index of the predecessor of X[k] in the longest increasing subsequence ending at X[k] 
 const pre = Array(n), memo = Array(n + 1) 
 let len = 0 // length
 for(let i = 0; i < n; i++) {
 let lo = 1, hi = len
 while(lo <= hi) {
 let mid = Math.ceil((lo + hi) / 2)
 if(arr[memo[mid]] < arr[i]) lo = mid + 1
 else hi = mid - 1
 }
 const newL = lo
 pre[i] = memo[newL - 1]
 memo[newL] = i
 if(newL > len) len = newL
 }
 const res = Array(len)
 let k = memo[len]
 for(let i = len - 1; i >= 0; i--) {
 res[i] = arr[k]
 k = pre[k]
 }
 return res
}
// construct. LIS
const LIS = X => {
 const n = X.length
 const P = Array(n), M = Array(n + 1)
 let L = 0
 for(let i = 0; i < n; i++) {
 let lo = 1, hi = L
 while(lo <= hi) {
 let mid = Math.ceil((lo + hi) / 2)
 if(X[M[mid]] < X[i]) lo = mid + 1
 else hi = mid - 1
 }
 let newL = lo
 P[i] = M[newL - 1]
 M[newL] = i
 if(newL > L) L = newL 
 }
 let S = Array(L)
 let k = M[L]
 for(let i = L - 1; i >= 0; i--) {
 S[i] = X[k]
 k = P[k]
 }
 return S
}
function constructLIS(arr) {
 const n = arr.length;
 const L = Array(n);
 for (let i = 0; i < L.length; i++) L[i] = [];
 L[0].push(arr[0]);
 for (let i = 1; i < n; i++) {
 for (let j = 0; j < i; j++) {
 if (arr[i] > arr[j] && L[i].length < L[j].length + 1) {
 L[i] = L[j].slice();
 }
 }
 L[i].push(arr[i]);
 }
 let max = L[0];
 for (let x of L) {
 if (x.length > max.length) max = x;
 }
 return max;
}
/**
 * @param {number[]} nums
 * @return {number}
 */
const lengthOfLIS = function(nums) {
 const stack = []
 for(let e of nums) {
 if(stack.length === 0 || e > stack[stack.length - 1]) {
 stack.push(e)
 continue
 }
 let l = 0, r = stack.length - 1, mid
 while(l < r) {
 const mid = l + ((r - l) >> 1)
 if(e > stack[mid]) l = mid + 1
 else r = mid
 }
 stack[l] = e
 }
 return stack.length
};

function convertFromBaseToBase(str, fromBase, toBase){
 const num = parseInt(str, fromBase);
 return num.toString(toBase);
}

function ceilIndex(t, l, r, key) {
 while (r - l > 1) {
 let m = (l + (r - l) / 2) >> 0
 if (t[m] >= key) {
 r = m
 } else {
 l = m
 }
 }
 return r
}
function floorIndex(t, l, r, key) {
 while (r - l > 1) {
 let m = (l + (r - l) / 2) >> 0
 if (t[m] <= key) {
 l = m
 } else {
 r = m
 }
 }
 return l
}

// the first element in the range [first, last) which has a value not less than val.
// This means that the function returns the index of the next smallest number just
// greater than or equal to that number. If there are multiple values that are equal to val,
// lower_bound() returns the index of the first such value.
// Like C++'s std::lower_bound. Returns the first index at which
// `value` could be inserted without changing the ordering. Assumes
// the array is sorted.
//
// `first` and `last` are indices and `less` is an optionally-specified
// function that returns true if
// array[i] < value
// for some i and false otherwise.
//
// Usage: lower_bound(array, value, [less])
// lower_bound(array, first, last, value, [less])
function lower_bound(array, arg1, arg2, arg3, arg4) {
 let first;
 let last;
 let value;
 let less;
 if (arg3 === undefined) {
 first = 0;
 last = array.length;
 value = arg1;
 less = arg2;
 } else {
 first = arg1;
 last = arg2;
 value = arg3;
 less = arg4;
 }
 if (less === undefined) {
 less = function (a, b) { return a < b; };
 }
 let len = last - first;
 let middle;
 let step;
 while (len > 0) {
 step = Math.floor(len / 2);
 middle = first + step;
 if (less(array[middle], value, middle)) {
 first = middle;
 first += 1;
 len = len - step - 1;
 } else {
 len = step;
 }
 }
 return first;
};

/**
It returns the first element in the range [first, last) that
is greater than value, or last if no such element is found.
*/
function upperBound(array, func) {
 let diff, len, i, current;
 len = array.length;
 i = 0;
 while (len) {
 diff = len >>> 1;
 current = i + diff;
 if (func(array[current])) {
 len = diff;
 } else {
 i = current + 1;
 len -= diff + 1;
 }
 }
 return i;
}

/**
 * Takes in a __SORTED__ array and inserts the provided value into
 * the correct, sorted, position.
 * @param array the sorted array where the provided value needs to be inserted (in order)
 * @param insertValue value to be added to the array
 * @param comparator function that helps determine where to insert the value (
 */
function binaryInsert(array, insertValue, comparator = (a, b) => a - b) {
 /*
 * These two conditional statements are not required, but will avoid the
 * while loop below, potentially speeding up the insert by a decent amount.
 * */
 if (array.length === 0 || comparator(array[0], insertValue) >= 0) {
 array.splice(0, 0, insertValue)
 return array;
 } else if (array.length > 0 && comparator(array[array.length - 1], insertValue) <= 0) {
 array.splice(array.length, 0, insertValue);
 return array;
 }
 let left = 0, right = array.length;
 let leftLast = 0, rightLast = right;
 while (left < right) {
 const inPos = Math.floor((right + left) / 2)
 const compared = comparator(array[inPos], insertValue);
 if (compared < 0) {
 left = inPos;
 } else if (compared > 0) {
 right = inPos;
 } else {
 right = inPos;
 left = inPos;
 }
 // nothing has changed, must have found limits. insert between.
 if (leftLast === left && rightLast === right) {
 break;
 }
 leftLast = left;
 rightLast = right;
 }
 // use right, because Math.floor is used
 array.splice(right, 0, insertValue);
 return array
}

function DFA(s) {
 let i = 1
 let j = 0
 const len = s.length
 const prefix = Array(len + 1).fill(0)
 prefix[0] = -1
 prefix[1] = 0
 while (i < len) {
 if (s[j] === s[i]) {
 j++
 i++
 prefix[i] = j
 } else {
 if (j > 0) j = prefix[j]
 else i++
 }
 }
 return prefix
}
function search(text, pattern) {
 let t = 0
 let p = 0
 const tLen = text.length
 const pLen = pattern.length
 const matches = []
 const prefix = DFA(pattern)
 while (t < tLen) {
 if (pattern[p] === text[t]) {
 p++
 t++
 if (p === pLen) {
 matches.push(t)
 p = prefix[p]
 }
 } else {
 p = prefix[p]
 if (p < 0) {
 t++
 p++
 }
 }
 }
 return matches
}

const lowBit = (x) => x & -x
class FenwickTree {
 constructor(n) {
 if (n < 1) return
 this.sum = Array(n + 1).fill(0)
 }
 update(i, delta) {
 if (i < 1) return
 while (i < this.sum.length) {
 this.sum[i] += delta
 i += lowBit(i)
 }
 }
 query(i) {
 if (i < 1) return
 let sum = 0
 while (i > 0) {
 sum += this.sum[i]
 i -= lowBit(i)
 }
 return sum
 }
}

class SegmentTree {
 /* Constructor to construct segment tree from given array. This 
 constructor allocates memory for segment tree and calls 
 constructSTUtil() to fill the allocated memory */
 constructor(arr, n) {
 // Allocate memory for segment tree
 //Height of segment tree
 const x = Math.ceil(Math.log(n) / Math.log(2))
 //Maximum size of segment tree
 const max_size = 2 * Math.pow(2, x) - 1
 this.st = new Array(max_size) // Memory allocation
 this.constructSTUtil(arr, 0, n - 1, 0)
 }
 // A utility function to get the middle index from corner indexes.
 getMid(s, e) {
 return s + (((e - s) / 2) >> 0)
 }
 /* A recursive function to get the sum of values in given range 
 of the array. The following are parameters for this function. 

 st --> Pointer to segment tree 
 si --> Index of current node in the segment tree. Initially 
 0 is passed as root is always at index 0 
 ss & se --> Starting and ending indexes of the segment represented 
 by current node, i.e., st[si] 
 qs & qe --> Starting and ending indexes of query range */
 getSumUtil(ss, se, qs, qe, si) {
 // If segment of this node is a part of given range, then return
 // the sum of the segment
 if (qs <= ss && qe >= se) return this.st[si]
 // If segment of this node is outside the given range
 if (se < qs || ss > qe) return 0
 // If a part of this segment overlaps with the given range
 const mid = this.getMid(ss, se)
 return (
 this.getSumUtil(ss, mid, qs, qe, 2 * si + 1) +
 this.getSumUtil(mid + 1, se, qs, qe, 2 * si + 2)
 )
 }
 /* A recursive function to update the nodes which have the given 
 index in their range. The following are parameters 
 st, si, ss and se are same as getSumUtil() 
 i --> index of the element to be updated. This index is in 
 input array. 
 diff --> Value to be added to all nodes which have i in range */
 updateValueUtil(ss, se, i, diff, si) {
 // Base Case: If the input index lies outside the range of
 // this segment
 if (i < ss || i > se) return
 // If the input index is in range of this node, then update the
 // value of the node and its children
 this.st[si] = this.st[si] + diff
 if (se != ss) {
 const mid = this.getMid(ss, se)
 this.updateValueUtil(ss, mid, i, diff, 2 * si + 1)
 this.updateValueUtil(mid + 1, se, i, diff, 2 * si + 2)
 }
 }
 // The function to update a value in input array and segment tree.
 // It uses updateValueUtil() to update the value in segment tree
 updateValue(arr, n, i, new_val) {
 // Check for erroneous input index
 if (i < 0 || i > n - 1) {
 return
 }
 // Get the difference between new value and old value
 const diff = new_val - arr[i]
 // Update the value in array
 arr[i] = new_val
 // Update the values of nodes in segment tree
 this.updateValueUtil(0, n - 1, i, diff, 0)
 }
 // Return sum of elements in range from index qs (quey start) to
 // qe (query end). It mainly uses getSumUtil()
 getSum(n, qs, qe) {
 // Check for erroneous input values
 if (qs < 0 || qe > n - 1 || qs > qe) {
 return -1
 }
 return this.getSumUtil(0, n - 1, qs, qe, 0)
 }
 // A recursive function that constructs Segment Tree for array[ss..se].
 // si is index of current node in segment tree st
 constructSTUtil(arr, ss, se, si) {
 // If there is one element in array, store it in current node of
 // segment tree and return
 if (ss == se) {
 this.st[si] = arr[ss]
 return arr[ss]
 }
 // If there are more than one elements, then recur for left and
 // right subtrees and store the sum of values in this node
 const mid = this.getMid(ss, se)
 this.st[si] =
 this.constructSTUtil(arr, ss, mid, si * 2 + 1) +
 this.constructSTUtil(arr, mid + 1, se, si * 2 + 2)
 return this.st[si]
 }
}
/**
const arr = [1, 3, 5, 7, 9, 11]
const n = arr.length
const t = new SegmentTree(arr, n)
const log = console.log
log(t.getSum(n, 1, 3))
t.updateValue(arr, n, 1, 10)
log(t.getSum(n, 1, 3))
*/

class UF {
 constructor(n) {
 this.root = Array(n).fill(null).map((_, i) => i)
 }
 find(x) {
 if (this.root[x] !== x) {
 this.root[x] = this.find(this.root[x])
 }
 return this.root[x]
 }
 union(x, y) {
 const xr = this.find(x)
 const yr = this.find(y)
 this.root[yr] = xr
 }
}
class UnionFind {
 constructor(n) {
 this.parents = Array(n)
 .fill(0)
 .map((e, i) => i + 1)
 this.ranks = Array(n).fill(0)
 }
 root(x) {
 while(x !== this.parents[x]) {
 this.parents[x] = this.parents[this.parents[x]]
 x = this.parents[x]
 }
 return x
 }
 find(x) {
 // if (x !== this.parents[x]) this.parents[x] = this.find(this.parents[x])
 // return this.parents[x]
 return this.root(x)
 }
 check(x, y) {
 return this.root(x) === this.root(y)
 }
 union(x, y) {
 const [rx, ry] = [this.find(x), this.find(y)]
 if (this.ranks[rx] >= this.ranks[ry]) {
 this.parents[ry] = rx
 this.ranks[rx] += this.ranks[ry]
 } else if (this.ranks[ry] > this.ranks[rx]) {
 this.parents[rx] = ry
 this.ranks[ry] += this.ranks[rx]
 }
 }
}

class PriorityQueue {
 constructor(comparator = (a, b) => a > b) {
 this.heap = []
 this.top = 0
 this.comparator = comparator
 }
 size() {
 return this.heap.length
 }
 isEmpty() {
 return this.size() === 0
 }
 peek() {
 return this.heap[this.top]
 }
 push(...values) {
 values.forEach((value) => {
 this.heap.push(value)
 this.siftUp()
 })
 return this.size()
 }
 pop() {
 const poppedValue = this.peek()
 const bottom = this.size() - 1
 if (bottom > this.top) {
 this.swap(this.top, bottom)
 }
 this.heap.pop()
 this.siftDown()
 return poppedValue
 }
 replace(value) {
 const replacedValue = this.peek()
 this.heap[this.top] = value
 this.siftDown()
 return replacedValue
 }
 parent = (i) => ((i + 1) >>> 1) - 1
 left = (i) => (i << 1) + 1
 right = (i) => (i + 1) << 1
 greater = (i, j) => this.comparator(this.heap[i], this.heap[j])
 swap = (i, j) => ([this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]])
 siftUp = () => {
 let node = this.size() - 1
 while (node > this.top && this.greater(node, this.parent(node))) {
 this.swap(node, this.parent(node))
 node = this.parent(node)
 }
 }
 siftDown = () => {
 let node = this.top
 while (
 (this.left(node) < this.size() && this.greater(this.left(node), node)) ||
 (this.right(node) < this.size() && this.greater(this.right(node), node))
 ) {
 let maxChild =
 this.right(node) < this.size() &&
 this.greater(this.right(node), this.left(node))
 ? this.right(node)
 : this.left(node)
 this.swap(node, maxChild)
 node = maxChild
 }
 }
}

function quickSort(arr) {
 // your code here
 sort(arr, 0, arr.length - 1)
}
function sort(arr, start, end) {
 if(start >= end) return
 const pivot = partition(arr, start, end)
 sort(arr, start, pivot - 1)
 sort(arr, pivot + 1, end)
}
function partition(arr, start, end) {
 const mid = arr[start]
 let l = start + 1, r = end
 while(l <= r) {
 if(arr[l] <= mid) l++
 else {
 swap(arr, l, r)
 r--
 }
 }
 swap(arr, start, r)
 return r
}
function swap(arr, i, j) {
 ;[arr[i], arr[j]] = [arr[j], arr[i]]
}

function QuickSelect(array, k, comparator) {
 const compare = comparator || defaultcomparator;
 if (array.length < k) {
 return array;
 }
 const idx = select(array, k, compare);
 if (idx !== k) console.log("could not complete quickselect");
 return array;
}
const defaultcomparator = (a, b) => a < b;
function swap(array, index1, index2) {
 const temp = array[index1];
 array[index1] = array[index2];
 array[index2] = temp;
}
function partition(array, leftindex, rightindex, pivotindex, compare) {
 const pivotvalue = array[pivotindex];
 swap(array, pivotindex, rightindex);
 let storeindex = leftindex;
 for (let i = leftindex; i < rightindex; i += 1) {
 if (compare(array[i], pivotvalue)) {
 swap(array, storeindex, i);
 storeindex += 1;
 }
 }
 swap(array, rightindex, storeindex);
 return storeindex;
}
function select(array, k, compare) {
 let leftindex = 0;
 let rightindex = array.length - 1;
 while (true) {
 if (leftindex == rightindex) return leftindex;
 let pivotindex = leftindex + Math.floor((rightindex - leftindex) / 2);
 pivotindex = partition(array, leftindex, rightindex, pivotindex, compare);
 if (k === pivotindex) return k;
 if (k < pivotindex) rightindex = pivotindex - 1;
 else leftindex = pivotindex + 1;
 }
}

/**
 * @param {number[]} arr
 */
function mergeSort(arr) {
 // your code here
 if(arr.length < 2) return
 const mid = Math.floor(arr.length / 2)
 const left = arr.slice(0, mid)
 const right = arr.slice(mid)
 mergeSort(left)
 mergeSort(right)
 let l = 0, r = 0
 while(l < left.length || r < right.length) {
 if(r === right.length || (l < left.length && left[l] <= right[r])) {
 arr[l + r] = left[l++]
 } else {
 arr[l + r] = right[r++]
 }
 }
}
// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
function merge(arr, l, m, r) {
 let i, j, k
 const n1 = m - l + 1
 const n2 = r - m
 /* create temp arrays */
 const L = Array(n1).fill(0)
 const R = Array(n2).fill(0)
 /* Copy data to temp arrays L[] and R[] */
 for (i = 0; i < n1; i++) L[i] = arr[l + i]
 for (j = 0; j < n2; j++) R[j] = arr[m + 1 + j]
 /* Merge the temp arrays back into arr[l..r]*/
 i = 0 // Initial index of first subarray
 j = 0 // Initial index of second subarray
 k = l // Initial index of merged subarray
 while (i < n1 && j < n2) {
 if (L[i] <= R[j]) {
 arr[k] = L[i]
 i++
 } else {
 arr[k] = R[j]
 j++
 }
 k++
 }
 /* Copy the remaining elements of L[], if there 
 are any */
 while (i < n1) {
 arr[k] = L[i]
 i++
 k++
 }
 /* Copy the remaining elements of R[], if there 
 are any */
 while (j < n2) {
 arr[k] = R[j]
 j++
 k++
 }
}
/* l is for left index and r is right index of the 
 sub-array of arr to be sorted */
function mergeSort(arr, l, r) {
 if (l < r) {
 // Same as (l+r)/2, but avoids overflow for
 // large l and h
 const m = l + ((r - l) >> 1)
 // Sort first and second halves
 mergeSort(arr, l, m)
 mergeSort(arr, m + 1, r)
 merge(arr, l, m, r)
 }
}

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
const BinarySearch = function(nums, target) {
 const n = nums.length
 let l = 0, r = n - 1
 while(l <= r) {
 const mid = l + ((r - l) >> 1)
 if(nums[mid] === target) return mid
 if(nums[mid] > target) r = mid - 1
 else l = mid + 1
 }
 return l
};
/**

Why return low rather than high?

The last iteration is lo == hi == mid
When target > nums[mid] == nums[lo] == nums[hi], after loop lo = lo + 1 == high +1 which will be the correct index for insertion
When target < nums[mid] == nums[lo] == nums[hi], after loop hi = hi - 1 == low - 1 is not the correct index, should be low


Why does Binary search algorithm use floor and not ceiling - not in an half open range?

This all depends on how you update your left and right variable.

Normally, we use left = middle+1 and right = middle-1, with stopping criteria left = right.

In this case, ceiling or flooring the middle value doesn't matter.

However, if we use left = middle+1 and right = middle, we must take the floor of the middle value, otherwise we end up in an endless loop.

Consider finding 11 in array 11, 22.

We set left = 0 and right = 1, the middle is 0.5, if we take the ceiling, it would be 1.
Since 22 is larger than query, we need to cut the right half and move right boarder towards middle.
This works fine when the array is large, but since there are only two elements.
right = middle will again set right to 1. We have an infinite loop.

To sum up,

both ceiling and flooring work fine with left = middle+1 and right = middle-1
ceiling works fine with left = middle and right = middle-1
flooring works fine with left = middle+1 and right = middle


*/

function binarySearch(arr, compareFn, target) {
 let left = 0; // inclusive
 let right = arr.length; // exclusive
 let found;
 while (left < right) {
 const middle = left + ((right - left) >> 1);
 const compareResult = compareFn(target, arr[middle]);
 if (compareResult > 0) {
 left = middle + 1;
 } else {
 right = middle;
 // We are looking for the lowest index so we can't return immediately.
 found = !compareResult;
 }
 }
 // left is the index if found, or the insertion point otherwise.
 // ~left is a shorthand for -left - 1.
 return found ? left : ~left;
};

function GCD(a, b) {
 if (a === 0) return b
 if (b === 0) return a
 return GCD(Math.abs(a - b), Math.min(a, b))
}
// or
function gcd(a, b) {
 return b ? gcd(b, a % b) : a
}
// or
function gcd(a, b) {
 while (b) {
 a %= b
 b = [a, (a = b)][0]
 }
 return a
}

function lcm(a, b) {
 return a / gcd(a, b) * b;
}
 
// another
function lcm(a, b) {
 return a * b / gcd(a, b);
}

function manachersAlgorithm(s, N) {
 const str = getModifiedString(s, N)
 const len = 2 * N + 1
 // expansion length
 const P = new Array(len).fill(0)
 // stores the center of the longest palindromic substring until now
 let c = 0
 // stores the right boundary of the longest palindromic substring until now
 let r = 0
 let maxLen = 0
 for (let i = 0; i < len; i++) {
 //get mirror index of i
 const mirror = 2 * c - i
 // see if the mirror of i is expanding beyond the left boundary
 // of current longest palindrome at center c
 // if it is, then take r - i as P[i]
 // else take P[mirror] as P[i]
 if (i < r) {
 P[i] = Math.min(r - i, P[mirror])
 }
 //expand at i
 let a = i + (1 + P[i])
 let b = i - (1 + P[i])
 while (a < len && b >= 0 && str.charAt(a) === str.charAt(b)) {
 P[i]++
 a++
 b--
 }
 // check if the expanded palindrome at i is expanding beyond the
 // right boundary of current longest palindrome at center c
 // if it is, the new center is i
 if (i + P[i] > r) {
 c = i
 r = i + P[i]
 if (P[i] > maxLen) {
 maxLen = P[i]
 }
 }
 }
 return maxLen
}
function getModifiedString(s, N) {
 let sb = ''
 for (let i = 0; i < N; i++) {
 sb += '#'
 sb += s.charAt(i)
 }
 sb += '#'
 return sb
}

function BinaryToGray(num) {
 // The operator >> is shift right. The operator ^ is exclusive or.
 return num ^ (num >> 1);
}
// This function converts a reflected binary Gray code number to a binary number.
function GrayToBinary(num) {
 let mask = num;
 // Each Gray code bit is exclusive-ored with all more significant bits.
 while (mask) {
 mask >>= 1;
 num ^= mask;
 }
 return num;
}
// A more efficient version for Gray codes 32 bits or fewer
// through the use of SWAR (SIMD within a register) techniques. 
// It implements a parallel prefix XOR function. The assignment
// statements can be in any order.
// 
// This function can be adapted for longer Gray codes by adding steps. 
function GrayToBinary32(num) {
 num ^= num >> 16;
 num ^= num >> 8;
 num ^= num >> 4;
 num ^= num >> 2;
 num ^= num >> 1;
 return num;
}

class TrieNode {
 constructor(v, isComplete = false) {
 this.val = v;
 this.isComplete = isComplete;
 this.children = new Map();
 }
}
class Trie {
 constructor() {
 this.head = new TrieNode(null);
 }
 /**
 * @param {string} word
 * @return {Trie}
 */
 addWord(word) {
 const characters = Array.from(word);
 let currentNode = this.head;
 for (let charIndex = 0; charIndex < characters.length; charIndex++) {
 const isComplete = charIndex === characters.length - 1;
 const char = characters[charIndex];
 if (currentNode.children.has(char)) {
 currentNode = currentNode.children.get(char);
 } else {
 const child = new TrieNode(char, isComplete);
 currentNode.children.set(char, child);
 currentNode = child;
 }
 }
 return this;
 }
 /**
 * @param {string} word
 * @return {Trie}
 */
 deleteWord(word) {
 const depthFirstDelete = (currentNode, charIndex = 0) => {
 if (charIndex >= word.length) {
 return;
 }
 const character = word[charIndex];
 const nextNode = currentNode.children.get(character);
 if (nextNode == null) {
 return;
 }
 depthFirstDelete(nextNode, charIndex + 1);
 if (charIndex === word.length - 1) {
 nextNode.isComplete = false;
 }
 // childNode is deleted only if:
 // - childNode has NO children
 // - childNode.isComplete === false
 if (nextNode.children.size === 0) {
 currentNode.children.delete(character);
 }
 };
 depthFirstDelete(this.head);
 return this;
 }
 /**
 * @param {string} word
 * @return {string[]}
 */
 suggestNextCharacters(word) {
 const lastCharacter = this.getLastCharacterNode(word);
 if (!lastCharacter) {
 return null;
 }
 return this.suggestChildren(lastCharacter);
 }
 /**
 * @param {TrieNode} node
 * @return {TrieNode}
 */
 suggestChildren(node) {
 if (node == null) return [];
 return [...node.children.keys()];
 }
 /**
 * Check if complete word exists in Trie.
 *
 * @param {string} word
 * @return {boolean}
 */
 doesWordExist(word) {
 const lastCharacter = this.getLastCharacterNode(word);
 return !!lastCharacter && lastCharacter.isComplete;
 }
 /**
 * @param {string} word
 * @return {TrieNode}
 */
 getLastCharacterNode(word) {
 const characters = Array.from(word);
 let currentNode = this.head;
 for (let charIndex = 0; charIndex < characters.length; charIndex++) {
 const char = characters[charIndex];
 if (!currentNode.children.has(char)) {
 return null;
 }
 currentNode = currentNode.children.get(char);
 }
 return currentNode;
 }
}

class BloomFilter {
 /**
 * @param {number} size - the size of the storage.
 */
 constructor(size = 100) {
 // Bloom filter size directly affects the likelihood of false positives.
 // The bigger the size the lower the likelihood of false positives.
 this.size = size
 this.storage = this.createStore(size)
 }
 /**
 * @param {string} item
 */
 insert(item) {
 const hashValues = this.getHashValues(item)
 hashValues.forEach((val) => this.storage.setValue(val))
 }
 /**
 * @param {string} item
 * @return {boolean}
 */
 mayContain(item) {
 const hashValues = this.getHashValues(item)
 for (let hashIndex = 0; hashIndex < hashValues.length; hashIndex += 1) {
 if (!this.storage.getValue(hashValues[hashIndex])) {
 return false
 }
 }
 return true
 }
 /**
 * @param {number} size
 * @return {Object}
 */
 createStore(size) {
 const storage = []
 for (
 let storageCellIndex = 0;
 storageCellIndex < size;
 storageCellIndex += 1
 ) {
 storage.push(false)
 }
 const storageInterface = {
 getValue(index) {
 return storage[index]
 },
 setValue(index) {
 storage[index] = true
 },
 }
 return storageInterface
 }
 /**
 * @param {string} item
 * @return {number}
 */
 hash1(item) {
 let hash = 0
 for (let charIndex = 0; charIndex < item.length; charIndex += 1) {
 const char = item.charCodeAt(charIndex)
 hash = (hash << 5) + hash + char
 hash &= hash
 hash = Math.abs(hash)
 }
 return hash % this.size
 }
 /**
 * @param {string} item
 * @return {number}
 */
 hash2(item) {
 let hash = 5381
 for (let charIndex = 0; charIndex < item.length; charIndex += 1) {
 const char = item.charCodeAt(charIndex)
 hash = (hash << 5) + hash + char
 }
 return Math.abs(hash % this.size)
 }
 /**
 * @param {string} item
 * @return {number}
 */
 hash3(item) {
 let hash = 0
 for (let charIndex = 0; charIndex < item.length; charIndex += 1) {
 const char = item.charCodeAt(charIndex)
 hash = (hash << 5) - hash
 hash += char
 hash &= hash
 }
 return Math.abs(hash % this.size)
 }
 /**
 * Runs all 3 hash functions on the input and returns an array of results.
 *
 * @param {string} item
 * @return {number[]}
 */
 getHashValues(item) {
 return [this.hash1(item), this.hash2(item), this.hash3(item)]
 }
}

function inverseElement(a, n) {
 let N = n
 if (GCD(a, n) == 1) {
 let p = 1,
 q = 0,
 r = 0,
 s = 1
 let c, quot, new_r, new_s
 while (n !== 0) {
 c = modulo(a, n)
 quot = Math.floor(a / n)
 a = n
 n = c
 new_r = p - quot * r
 new_s = q - quot * s
 p = r
 q = s
 r = new_r
 s = new_s
 }
 return modulo(p, N)
 } else {
 return null
 }
}
function modulo(a, n) {
 if (a >= 0) {
 return a % n
 } else {
 return (a % n) + n
 }
}
// another
function inverseElement(a, b) {
 return quickPow(a, b - 2) % b
}
function quickPow(a, b) {
 let ans = 1;
 a = (a % p + p) % p;
 for (; b; b >>= 1) {
 if (b & 1) ans = (a * ans) % p;
 a = (a * a) % p;
 }
 return ans;
}

/**
 * @param {number} maxNumber
 * @return {number[]}
 */
export default function sieveOfEratosthenes(maxNumber) {
 const isPrime = new Array(maxNumber + 1).fill(true);
 isPrime[0] = false;
 isPrime[1] = false;
 const primes = [];
 for (let number = 2; number <= maxNumber; number += 1) {
 if (isPrime[number] === true) {
 primes.push(number);
 let nextNumber = number * 2;
 while (nextNumber <= maxNumber) {
 isPrime[nextNumber] = false;
 nextNumber += number;
 }
 }
 }
 return primes;
}

function squareRoot(number, tolerance = 0.0001) {
 if (number < 0) {
 return null;
 }
 if (number === 0) {
 return 0;
 }
 let root = 1;
 const requiredDelta = 1 / (10 ** tolerance);
 while (Math.abs(number - (root ** 2)) > requiredDelta) {
 root -= ((root ** 2) - number) / (2 * root);
 }
 return Math.round(root * (10 ** tolerance)) / (10 ** tolerance);
}

function isPowerOfTwoBitwise(number) {
 if (number < 1) return false
 return (number & (number - 1)) === 0;
}

function integerPartition(number) {
 const partitionMatrix = Array(number + 1)
 .fill(null)
 .map(() => {
 return Array(number + 1).fill(null)
 })
 for (let numberIndex = 1; numberIndex <= number; numberIndex++) {
 partitionMatrix[0][numberIndex] = 0
 }
 for (let summandIndex = 0; summandIndex <= number; summandIndex++) {
 partitionMatrix[summandIndex][0] = 1
 }
 for (let summandIndex = 1; summandIndex <= number; summandIndex++) {
 for (let numberIndex = 1; numberIndex <= number; numberIndex++) {
 if (summandIndex > numberIndex) {
 partitionMatrix[summandIndex][numberIndex] =
 partitionMatrix[summandIndex - 1][numberIndex]
 } else {
 const combosWithoutSummand =
 partitionMatrix[summandIndex - 1][numberIndex]
 const combosWithSummand =
 partitionMatrix[summandIndex][numberIndex - summandIndex]
 partitionMatrix[summandIndex][numberIndex] =
 combosWithoutSummand + combosWithSummand
 }
 }
 }
 return partitionMatrix[number][number]
}

function power(base, power) {
 if (power === 0) return 1
 if (power % 2 === 0) {
 const multiplier = fastPowering(base, power / 2)
 return multiplier * multiplier
 }
 const multiplier = fastPowering(base, Math.floor(power / 2))
 return multiplier * multiplier * base
}

// combinations without repetition
function comb(n, r) {
 if (n < r) return 0;
 let res = 1;
 if (n - r < r) r = n - r;
 for (let i = n, j = 1; i >= 1 && j <= r; --i, ++j) {
 res = res * i;
 }
 for (let i = r; i >= 2; --i) {
 res = res / i;
 }
 return res;
}

// Bell triangle method
function bellNumber(n) {
 const bell = Array.from({ length: n + 1 }, () => Array(n + 1).fill(0))
 bell[0][0] = 1
 for (let i = 1; i <= n; i++) {
 bell[i][0] = bell[i - 1][i - 1]
 for (let j = 1; j <= i; j++)
 bell[i][j] = bell[i - 1][j - 1] + bell[i][j - 1]
 }
 return bell[n][0]
}

// Returns count of different partitions of n
// elements in k subsets
function countP(n, k) {
 const dp = Array.from({ length: n + 1 }, () => Array(k + 1).fill(0))
 // Base cases
 for (let i = 0; i <= n; i++) dp[i][0] = 0
 for (let i = 0; i <= k; i++) dp[0][k] = 0
 // Bottom up
 for (let i = 1; i <= n; i++) {
 for (let j = 1; j <= k; j++) {
 if (j == 1 || i == j) dp[i][j] = 1
 else dp[i][j] = j * dp[i - 1][j] + dp[i - 1][j - 1]
 }
 }
 return dp[n][k]
}

class TreeSet {
 constructor(comparator) {
 this.length = 0
 this.elements = []
 if (comparator) this.comparator = comparator
 else this.comparator = (a, b) => a > b ? 1 : (a < b ? -1 : 0)
 }
 size() {
 return this.elements.length
 }
 last() {
 return this.elements[this.length - 1]
 }
 first() {
 return this.elements[0]
 }
 isEmpty() {
 return this.size() === 0
 }
 pollLast() {
 if (this.length > 0) {
 this.length--
 return this.elements.splice(this.length, 1)
 }
 return null
 }
 pollFirst() {
 if (this.length > 0) {
 this.length--
 return this.elements.splice(0, 1)
 }
 return null
 }
 add(element) {
 let index = this.binarySearch(element)
 if(index >= 0) return
 index = -index - 1
 this.elements.splice(index, 0, element)
 this.length++
 }
 /**
 * Performs a binary search of value in array
 * @param {number[]} array - Array in which value will be searched. It must be sorted.
 * @param {number} value - Value to search in array
 * @return {number} If value is found, returns its index in array. Otherwise, returns
 * a negative number indicating where the value should be inserted: -(index + 1)
 */
 binarySearch(value) {
 let low = 0
 let high = this.elements.length - 1
 while (low <= high) {
 let mid = low + ((high - low) >>> 1)
 let midValue = this.elements[mid]
 let cmp = this.comparator(midValue, value)
 if (cmp < 0) low = mid + 1
 else if (cmp > 0) high = mid - 1
 else return mid
 }
 return -(low + 1)
 }
}