class MultiSet:
    def __init__(self):
        self.data = dict()
    
    def add(self, val):
        self.data[val] = 1 + (self.data[val] if val in self.data else 0)
    
    def remove(self, val):
        if not val in self.data:
            return
        self.data[val] -= 1
        if self.data[val] == 0:
            del self.data[val]

class BIT:
    def __init__(self, size):
        self.size = size
        self.data = [0] * size
    
    def add(self, pos, val):
        while pos < self.size:
            self.data[pos] += val
            pos += pos & (-pos)
    
    def query(self, pos):
        res = 0
        while pos > 0:
            res += self.data[pos]
            pos &= pos - 1
        return res

def kgcd(a, b):
        if a == 0:
            return b
        if b == 0:
            return a
        if (a & 1) == 0 and (b & 1) == 0:
            return kgcd(a >> 1, b >> 1) << 1
        elif (b & 1) == 0:
            return kgcd(a, b >> 1)
        elif (a & 1) == 0:
            return kgcd(a >> 1, b)
        else:
            return kgcd(abs(a - b), min(a, b))