class FenwickTree:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)  # 1-based indexing
    
    def update(self, index, delta):
        """Add delta to index i"""
        index += 1  # Convert to 1-based indexing
        while index <= self.size:
            self.tree[index] += delta
            index += index & (-index)  # Add LSB
    
    def prefix_sum(self, index):
        """Get sum from index 1 to index"""
        index += 1  # Convert to 1-based indexing
        total = 0
        while index > 0:
            total += self.tree[index]
            index -= index & (-index)  # Remove LSB
        return total
    
    def range_sum(self, left, right):
        """Get sum from index left to index right (inclusive)"""
        return self.prefix_sum(right) - self.prefix_sum(left - 1)
    
    def get(self, index):
        """Get value at index"""
        return self.range_sum(index, index)

class FenwickTree2D:
    def __init__(self, n, m):
        self.n = n
        self.m = m
        self.tree = [[0] * (m + 1) for _ in range(n + 1)]
    
    def update(self, x, y, delta):
        x += 1  # Convert to 1-based indexing
        y += 1
        i = x
        while i <= self.n:
            j = y
            while j <= self.m:
                self.tree[i][j] += delta
                j += j & (-j)
            i += i & (-i)
    
    def prefix_sum(self, x, y):
        x += 1  # Convert to 1-based indexing
        y += 1
        total = 0
        i = x
        while i > 0:
            j = y
            while j > 0:
                total += self.tree[i][j]
                j -= j & (-j)
            i -= i & (-i)
        return total
    
    def range_sum(self, x1, y1, x2, y2):
        return (self.prefix_sum(x2, y2) - 
                self.prefix_sum(x2, y1 - 1) - 
                self.prefix_sum(x1 - 1, y2) + 
                self.prefix_sum(x1 - 1, y1 - 1))

class RangeUpdateFenwickTree:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
        self.tree2 = [0] * (n + 1)  # For handling range updates
    
    def _update(self, index, value, tree):
        while index <= self.size:
            tree[index] += value
            index += index & (-index)
    
    def range_update(self, left, right, value):
        """Add value to range [left, right]"""
        self._update(left + 1, value, self.tree)
        self._update(right + 2, -value, self.tree)
        self._update(left + 1, value * left, self.tree2)
        self._update(right + 2, -value * (right + 1), self.tree2)
    
    def _query(self, index, tree):
        total = 0
        while index > 0:
            total += tree[index]
            index -= index & (-index)
        return total
    
    def get(self, index):
        """Get value at index"""
        index += 1
        return self._query(index, self.tree) * index - self._query(index, self.tree2)

class OrderStatisticTree:
    def __init__(self, max_val):
        self.size = max_val
        self.tree = [0] * (max_val + 1)
    
    def insert(self, value):
        """Insert a value"""
        self.update(value, 1)
    
    def delete(self, value):
        """Delete a value"""
        self.update(value, -1)
    
    def update(self, value, delta):
        while value <= self.size:
            self.tree[value] += delta
            value += value & (-value)
    
    def find_kth(self, k):
        """Find kth smallest element"""
        pos = 0
        total = 0
        for i in range(self.size.bit_length() - 1, -1, -1):
            if pos + (1 << i) <= self.size:
                if total + self.tree[pos + (1 << i)] < k:
                    total += self.tree[pos + (1 << i)]
                    pos += (1 << i)
        return pos + 1

def handle_empty(self):
    return self.size == 0 or all(v == 0 for v in self.tree[1:])

def handle_single(self):
    if self.size == 1:
        return self.tree[1]

def validate_range(self, left, right):
    if not 0 <= left <= right < self.size:
        raise ValueError("Invalid range")

class OptimizedFenwickTree:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
    
    def lsb(self, x):
        return x & (-x)
    
    def update(self, index, delta):
        index += 1
        while index <= self.size:
            self.tree[index] += delta
            index += self.lsb(index)

class BulkUpdateFenwickTree(FenwickTree):
    def bulk_update(self, updates):
        # Sort updates by index for better cache utilization
        updates.sort(key=lambda x: x[0])
        for index, delta in updates:
            self.update(index, delta)

class SparseFenwickTree:
    def __init__(self):
        self.tree = {}
    
    def update(self, index, delta):
        while index in self.tree:
            self.tree[index] += delta
            index += index & (-index)
    
    def prefix_sum(self, index):
        total = 0
        while index > 0:
            total += self.tree.get(index, 0)
            index -= index & (-index)
        return total

from array import array

class CompactFenwickTree:
    def __init__(self, n):
        self.size = n
        # Use array module for memory efficiency
        self.tree = array('l', [0] * (n + 1))

class CacheFriendlyFenwickTree:
    def __init__(self, n):
        self.size = n
        self.block_size = 64 // 8  # Cache line size
        self.tree = [0] * (n + 1)
    
    def update(self, index, delta):
        index += 1
        block = index // self.block_size
        while index <= self.size:
            self.tree[index] += delta
            next_block = (index + (index & (-index))) // self.block_size
            if next_block != block:
                break
            index += index & (-index)

from concurrent.futures import ThreadPoolExecutor

class ParallelFenwickTree:
    def bulk_update_parallel(self, updates, num_threads=4):
        def update_chunk(chunk):
            for index, delta in chunk:
                self.update(index, delta)
        
        chunk_size = len(updates) // num_threads
        chunks = [updates[i:i + chunk_size] for i in range(0, len(updates), chunk_size)]
        
        with ThreadPoolExecutor(max_workers=num_threads) as executor:
            executor.map(update_chunk, chunks)

# Wrong
def update_wrong(self, index, delta):
    while index < len(self.tree):  # Wrong condition
        self.tree[index] += delta
        index += index & (-index)

# Correct
def update_correct(self, index, delta):
    index += 1  # Convert to 1-based indexing
    while index <= self.size:
        self.tree[index] += delta
        index += index & (-index)

# Wrong
def range_update_wrong(self, left, right, value):
    for i in range(left, right + 1):
        self.update(i, value)  # O(n log n) complexity

# Correct
def range_update_correct(self, left, right, value):
    self._update(left, value)
    self._update(right + 1, -value)

# Wrong
def prefix_sum_wrong(self, index):
    total = 0
    while index > 0:
        total += self.tree[index]  # Possible overflow
        index -= index & (-index)
    return total

# Correct
def prefix_sum_correct(self, index):
    total = 0
    while index > 0:
        total = (total + self.tree[index]) % (10**9 + 7)  # Handle overflow
        index -= index & (-index)
    return total