"""
基本思想：
    按照wi+si的和从小到大的顺序排列时，最大的风险系数一定最小
反证法证明：
    假设wi+si>w(i+1)+s(i+1),即不满足从小到大排序，则比较交换第i个位置和第i+1个位置的牛前后，风险系数的变化，发现交换前最大风险系数的最小值要大于交换后最大风险系数的最小值
"""

if __name__=="__main__":
    n = int(input().strip())
    cows = []
    for _ in range(n):
        w, s = map(int, input().split())
        cows.append((w, s))

    # 升序排序
    cows.sort(key = lambda x:x[0]+x[1])

    res = -2e9
    su = 0    # 存储前面牛的体重和
    for w, s in cows:
        res = max(res, su-s)    # 前面牛的体重和-当前牛的强壮程度
        su += w
    print(res)

"""
基本思想：
    假设数轴上共有n个点，坐标分别为x1, x2, x3,...,xn，同时设货仓的位置为x，
    则货仓到所有点的距离和为f(x) = |x1-x|+|x2-x|+|x3-x|+...+|xn-x|,
    整理得f(x) = (|x1-x|+|xn-x|)+(|x2-x|+|x'n-1'-x|)+...
    根据绝对值不等式g(x) = |a-x|+|b-x|当x取在a,b之间时，函数值最小，
    所以有f(x) >= xn-x1 + x'n-1'-x2 + ...,
    所以，当x取到所有对数之间时，也就是中位数时，f(x)能取到极小值
"""
if __name__=="__main__":
    n = int(input().strip())
    a = list(map(int, input().split()))
    a.sort()

    res = 0
    x = a[n//2]
    for item in a:
        res += abs(item - x)
    print(res)

"""
基本思想：
    当事件ti从小到大递增时，排队时间最小；
    因此，先将等待时间序列从小到大排序，然后根据T = t1*(n-1)+t2*(n-2)+t3*(n-3)...+tn*(n-n),计算需要等待的最短总时间
"""
if __name__=="__main__":
    n = int(input().strip())
    t = [0]    # 用0填充补位
    t.extend(list(map(int, input().split())))

    t.sort()

    res = 0
    for i in range(1, n+1):
        res += t[i]*(n-i)
    print(res)

"""
基本思想：
    将合并过程看做一个Huffman树（完全二叉树）；
    最小的两个点， 深度一定最深，且可以互为兄弟；
    每次合并值最小的两个点，然后将两个点的和添加进堆中。
"""
import heapq

if __name__=="__main__":
    n = int(input().strip())
    heap = list(map(int, input().split()))

    res = 0
    heapq.heapify(heap)
    while len(heap)>1:
        a = heapq.heappop(heap)
        b = heapq.heappop(heap)
        su = a+b
        res+=su
        heapq.heappush(heap, su)

    print(res)

"""
基本思想：
    1. 将所有区间按照左端点从小到大排序(为什么要按照区间的左端点排序，这样遍历时需要确定左端点是够能够覆盖掉目标区间的start)
    2. 遍历每个区间，在所有能覆盖掉start的区间中，选择右端点r最大的区间，更新start=r
"""

if __name__=="__main__":
    st, ed = map(int, input().split())
    n = int(input().strip())

    ranges = []
    for _ in range(n):
        a, b = map(int, input().split())
        ranges.append((a, b))
    ranges.sort(key=lambda x:x[0])

    res = 0
    flag = False    # flag用来标记区间是否被覆盖
    i = 0
    while i<n:
        j = i
        r = -2e9    # ！！！技巧：r可以初始化为很小的数
        while j<n and ranges[j][0]<=st:
            r = max(r, ranges[j][1])    # ！！！出错：写成r = max(st, ranges[j][1])会报错
            j += 1
        if r<=st:    # 没有能覆盖st的区间
            flag = False
            res = -1
            break
        res += 1
        if r>=ed:
            flag = True
            break
        st = r    # ！！！出错：忘记更新start
        i = j - 1
    if flag==False: print(-1)
    else: print(res)

"""
基本思想：
    1. 将所有区间按照左端点从小到大排序(为什么要按照区间的左端点排序？？？)
    2. 遍历每一个区间，并使用一个小根堆来维护每一组区间的右端点的最大值max_r：
        2.1 如果当前区间的左端点l>小根堆的最小值，则可以将当前区间添加到组中，并更新组的max_r；
        2.2 如果当前区间的左端点l<=小根堆的最小值,则需要开新组，然后将当前区间的右端点r添加到小根堆中
"""
import heapq
if __name__=="__main__":
    n = int(input().strip())

    ranges = []
    for _ in range(n):
        a, b = map(int, input().split())
        ranges.append((a, b))

    # 初始化小根堆,默认小根堆
    h = []

    ranges.sort(key=lambda x:x[0])

    end = -2e9
    for l, r in ranges:
        if not h or h[0]>=l:    # 2.2 如果当前区间的左端点l<=小根堆的最小值,则需要开新组，然后将当前区间的右端点r添加到小根堆中
            heapq.heappush(h, r)
        else:
            #if h[0]<r:    # 如果h[0]<l,那么h[0]<r肯定成立，所以不需要加if判断
            heapq.heappop(h)
            heapq.heappush(h, r)
    print(len(h))

"""
基本思想：
    1. 将所有区间按照右端点从小到大排序(为什么要按照区间的右端点排序？因为区间的右端点能够判断出与要遍历的区间是否相交)
    2. 维护当前区间的右端点end，遍历每一个区间的左端点：
        2.1 如果当前区间的右端点end>=遍历区间的左端点，则两个区间相交，可以直接pass；
        2.2 如果当前区间的右端点end<遍历区间的左端点,则不想交的区间数加1，end更新为正在遍历区间的右端点r
"""

if __name__=="__main__":
    n = int(input().strip())

    ranges = []
    for _ in range(n):
        a, b =map(int, input().split())
        ranges.append((a, b))

    # 按照区间右端点排序
    ranges.sort(key=lambda x:x[1])

    res = 0
    end = -2e9
    for l, r in ranges:
        if end<l:
            res += 1
            end = r
    print(res)

"""
基本思想：
    1. 将所有区间按照右端点从小到大排序(为什么要按照区间的右端点排序？因为区间的右端点能够覆盖尽可能多的区间)
    2. 维护当前区间的右端点end，遍历每一个区间的左端点：
        2.1 如果当前区间的右端点end>=遍历区间的左端点，则不需要新加一个点，可以直接pass；
        2.2 如果当前区间的右端点end<遍历区间的左端点,则点数加1
"""

if __name__=="__main__":
    n = int(input().strip())
    ranges = []
    for _ in range(n):
        a, b = map(int, input().split())
        ranges.append((a, b))
    ranges.sort(key=lambda x:x[1])

    res = 0
    end = -2e9
    for l, r in ranges:
        if end<l:
            res += 1
            end = r
    print(res)

"""
作用：
    计算得到一个x，使得ax=b(mod m)

基本思想：线性同余方程求解x，可转化成ax+my=b，然后利用扩展欧几里得算法求解
    因为 a∗x≡b(mod m)，所以a*x = b + m*y,即a*x-m*y=b，
    令y‘ = -y，则有a*x+m*y=b，求x。
    解存在的条件：当(a, b)%d==0时，有解，否则无解
"""
def exgcd(a, b):
    global x, y
    if b==0:
        x = 1; y = 0    # 当b==0时，x = 1，y = 0；
        return a
    else:
        d =  int(exgcd(b, a % b))
        # 颠倒x和y的顺序, tmp存x，x存y
        tmp = x
        x = y
        y = tmp-(a//b)*y    # y = y-(a//b)*x, 更新y时，更新公式里的y对应x(tmp)，x对应y
        return d

if __name__=="__main__":
    n = int(input().strip())
    for _ in range(n):
        a, b, m = map(int, input().split())
        x = 0
        y = 0
        d = exgcd(a, m)
        if b % d: print("impossible")
        else: print((int(b/d)*x%m))    # ！！！注意：一定要写成int(b/d)*x%m，而不能写成int(b/d*x%m)，否则会报错

"""
算法作用：
    欧几里得算法中，根据裴蜀定理，对于任意两个正整数a,b,一定存在整数x，y，使得ax+by = (a,b),其中(a,b)表示a和b的最大公约数
    扩展欧几里得算法就是用来求上式的一组系数x，y
    即，求x, y，使得ax + by = gcd(a, b)
算法原理：
    在欧几里得算法模板上进行修改：
        当b==0时，x = 1，y = 0；
        当b!=0时，x不变，y = y-(a//b)*x
"""
def exgcd(a, b):
    global x, y
    if b==0:
        x = 1; y = 0    # 当b==0时，x = 1，y = 0；
        return a
    else:
        d =  int(exgcd(b, a % b))
        # 颠倒x和y的顺序, tmp存x，x存y
        tmp = x
        x = y
        y = tmp-(a//b)*y    # y = y-(a//b)*x, 更新y时，更新公式里的y对应x(tmp)，x对应y
        return d

if __name__=="__main__":
    n = int(input().strip())
    for _ in range(n):
        a, b = map(int, input().split())
        # 初始化系数x，y
        x = 0
        y = 0

        exgcd(a, b)
        print(x, y)