Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

n, c = list(map(int, input().split()))
sushi1 = []
sushi2 = []
c1 = []
c2 = []
c3 = []
c4 = []
k1 = 0
k2 = 0
for i in range(n):
    x, v = list(map(int, input().split()))
    sushi1.append((x, v))
    sushi2.append((c-x, v))
sushi1.sort()
sushi2.sort()
for j in range(n):
    k1 += sushi1[j][1]
    k2 += sushi2[j][1]
    c1.append(k1-sushi1[j][0])
    c2.append(k2-sushi2[j][0])
for k in range(n-1):
    c3.append(c1[k]+max(c2[:n-k-1])-sushi1[k][0])
    c4.append(c2[k]+max(c1[:n-k-1])-sushi2[k][0])
print(max(c1+c2+c3+c4+[0]))

### FIXED CODE ###

import numpy as np
n, c = list(map(int, input().split()))
xv = list(list(map(int, input().split())) for i in range(n))
sushi1, max1, sushi2, max2 = [0], [0], [0], [0]
sum1, sum2 = 0, 0
for x, v in xv:
    sum1 += v
    sushi1.append(max(sum1 - x, sushi1[-1]))
    max1.append(max(sum1 - 2*x, max1[-1]))
for x, v in xv[::-1]:
    sum2 += v
    sushi2.append(max(sum2 - (c-x), sushi2[-1]))
    max2.append(max(sum2 - 2*(c-x), max2[-1]))
ans1 = max(np.array(sushi1) + np.array(max2[::-1]))
ans2 = max(np.array(sushi2) + np.array(max1[::-1]))
print(max(0, ans1, ans2))
### BUGGY CODE ###

import heapq
import itertools

x,y,z,k=(int(i) for i in input().split())
#print(x,y,z,k)
a=list((-1)*int(i) for i in input().split())
#a.sort(reverse=True)
b=list((-1)*int(i) for i in input().split())
#b.sort(reverse=True)
c=list((-1)*int(i) for i in input().split())
#c.sort(reverse=True)
#print(a,b,c)

mylist=list(itertools.product(a,b,c))
#print(mylist)
mylist=[sum(mylist[i]) for i in range(len(mylist))]
#print(mylist)

def heapsort(iterable):
    h = []
    for value in iterable:
        heapq.heappush(h, value)
    return [heapq.heappop(h) for i in range(k)]

#    return [heapq.heappop(h) for i in range(len(h))]

#heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
mylist1=heapsort(mylist)

for i in range(k):
  print((-1)*mylist1[i])
  

### FIXED CODE ###

#import itertools

x,y,z,k=(int(i) for i in input().split())
#print(x,y,z,k)
a=list(int(i) for i in input().split())
a.sort(reverse=True)
b=list(int(i) for i in input().split())
b.sort(reverse=True)
c=list(int(i) for i in input().split())
c.sort(reverse=True)
#print(a,b,c)

#k=3000
#a=[int(i) for i in range(1000)]
#b=[int(i) for i in range(1000)]
#c=[int(i) for i in range(1000)]
x=[]
for h in range(len(a)):
    for i in range(len(b)):
        if (h+1)*(i+1) <=k:
            for j in range(len(c)):
                if (h+1)*(i+1)*(j+1) <=k:
                    x.append(a[h]+b[i]+c[j])

x.sort(reverse=True)
for i in range(k):
  print(x[i])
### BUGGY CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

def gcd_list(numbers):
    return reduce(math.gcd, numbers)

K = int(input())

a = 1
b = 1
c= 1
ans = 0

while a <= K:
  b = 1
  while b <= K:
    c = 1
    while c <=K:
      if gcd(a, b) == 1:
        ans += 1
      else:
        ans += gcd(a, b, c)
      c += 1
    b += 1
  a += 1
print(ans)

### FIXED CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

def gcd_list(numbers):
    return reduce(math.gcd, numbers)

K = int(input())

a = 1
b = 1
c= 1
ans = 0

while a <= K:
  b = 1
  while b <= K:
    c = 1
    while c <=K:
      if gcd(a, b) == 1:
        ans += 1
      else:
        ans += gcd(a, b, c)
      c += 1
    b += 1
  a += 1
print(ans)
### BUGGY CODE ###

def check(sum, i, j, size):
    s = sum[i][j] - sum[i - size][j] - sum[i][j - size] + sum[i - size][j - size]
    return s == 0

def mm(sum, n, size):
    for i in xrange(size, n + 1):
            for j in xrange(size, n + 1):
                if check(sum, i, j, size):
                    return True
    return False

def m(sum, n):
    r = 0
    left, mid, right = 0, 0, n
    while left <= right:
        mid = (left + right) / 2
        if mm(sum, n, mid):
            r = max(r, mid)
            left = mid + 1
        else:
            if left == right:
                break
            right = mid
    return r

while True:
    n = int(raw_input())
    if n == 0:
        break
    s = [map(int, raw_input().replace('.','0').replace('*','1')) for i in xrange(n)]
    sum = [[0] * (n + 1) for i in xrange(n + 1)]
    for i in xrange(1, n + 1):
        for j in xrange(1, n + 1):
            sum[i][j] += s[i - 1][j - 1]
            sum[i][j] += (sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1])
    print m(sum, n)

### FIXED CODE ###

while True:
    n = int(raw_input())
    if n == 0:
        break
    s = [raw_input() for i in range(n)]
    dp = [[0] * (n + 1) for i in range(n + 1)]
    for i in range(n):
        for j in range(n):
            if s[i][j] == '.':
                dp[i][j] = min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) + 1
    print max(map(max, dp))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(pow(10, 6))

N, M = map(int, input().split())
R = []
for _ in range(N):
    a, b = map(int, input().split())
    R.append((a*2, b, 0, 0))
for i in range(M):
    l, r = map(int, input().split())
    R.append((l*2-1, 2, -1, i))
    R.append((r*2+1, 3, 2*l-1, i))

R.sort(key=lambda x:x[0])
nodeid = 0
bf = -1
d = dict()
x2id = dict()
id2eid = dict()
G = [set()]
for x, f, l, i in R:
    if f <= 1:
        d[nodeid] = int(f != bf and bf != -1)
        bf = f
        nodeid += 1
        G.append(set())
    else:
        x2id[x] = nodeid
        if f == 3:
#            print(x2id, l)
            G[nodeid].add(x2id[l])
            G[x2id[l]].add(nodeid)
            id2eid[(nodeid, x2id[l])] = i
            id2eid[(x2id[l], nodeid)] = i
d[nodeid] = int(bf == 1)

def iterf(v):
    r = d[v]
    for u in G[v]:
        if u in vs:
            continue
        vs.add(u)
        ff = iterf(u)
        if ff:
            cut_edges.add((v, u))
        r = (r+ff)%2
    return r if v != 0 else 0

xxs = [-1]*nodeid
vs = set()
cut_edges = set()
for i in range(nodeid+1):
    if i in vs:
        continue
    vs.add(i)
    rr = iterf(i)
    if rr:
        print(-1)
        break
else:
    print(len(cut_edges))
    print(*sorted(id2eid[(x, y)]+1 for x, y in cut_edges))


### FIXED CODE ###

import sys
input = sys.stdin.readline
LLL = 1<<20

N, M = map(int, input().split())
R = []
for _ in range(N):
    a, b = map(int, input().split())
    R.append((a*2, b, 0))
for i in range(M):
    l, r = map(int, input().split())
    R.append((l*2-1, 2, i))
    R.append((r*2+1, 3, i))

R.sort(key=lambda x:x[0])
nodeid = 0
bf = -1
d = []
eid2lid = dict()
id2eid = dict()
G = [set()]
for x, f, i in R:
    if f <= 1:
        d.append(int(f != bf and bf != -1))
        bf = f
        nodeid += 1
        G.append(set())
    else:
        if f == 3:
#            print(x2id, l)
            lid = eid2lid[i]
            if nodeid != lid:
                G[nodeid].add((lid, i+1))
                G[lid].add((nodeid, i+1))
#                id2eid[lid*LLL+nodeid] = i
#            id2eid[(n2, n1)] = i
        eid2lid[i] = nodeid
d.append(int(bf==1))

xxs = [-1]*(nodeid+1)
g2 = [set() for _ in range(nodeid+1)]
vs = set()
cut_edges = set()
for i in range(nodeid+1):
    if i in vs:
        continue
    stack = [i]
    dfs_vs = []
    vs.add(i)
    while stack:
        v = stack.pop()
        dfs_vs.append(v)
        for u, j in G[v]:
            if u in vs:
                continue
            g2[v].add((u, j))
            stack.append(u)
            vs.add(u)
    for v in dfs_vs[::-1]:
        r = d[v]
        for u, j in g2[v]:
            ff = xxs[u]
            if ff:
                cut_edges.add(j)
            r = (r+ff)%2
        xxs[v] = r if v != 0 else 0
    if xxs[i]:
        print(-1)
        break
else:
    print(len(cut_edges))
    print(*sorted(cut_edges))
### BUGGY CODE ###

import collections
def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

n,x,y = map(int,input().split()) #n:頂点数　w:辺の数

d = [[float("inf")]*n for i in range(n)]
#d[u][v] : 辺uvのコスト(存在しないときはinf)

for i in range(n-1):
    d[i][i+1] = 1
    d[i+1][i] = 1
d[x-1][y-1] = 1
d[y-1][x-1] = 1

for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０
k=0

for i in range(n):
    if i==0:
        continue
    for j in range(n):
        k=k+collections.Counter(warshall_floyd(d)[j])[i]
    print(k//2)
    k=0


### FIXED CODE ###

from collections import *
from heapq import *
from itertools import *
from fractions import gcd
import sys
from decimal import *
import copy
from bisect import *

input = lambda: sys.stdin.readline().rstrip()

N, X, Y = map(int, input().split())
data = [[] for i in range(N + 1)]
for i in range(1, N):
    a = i
    b = i + 1
    data[a].append(b)
    data[b].append(a)
data[X].append(Y)
data[Y].append(X)

dic = defaultdict(int)
for i in range(1,N+1):
    stack=deque([[i,0]])
    visited=set()
    visited.add(i)
    count=set()
    while stack:
        now, dist=stack.popleft()
        for j in data[now]:
            if not j in visited:
                #print(stack)
                visited.add(j)
                stack.append([j,dist+1])
                dic[dist+1]+=1
for k in range(1,N):
    print(dic[k]//2)
### BUGGY CODE ###

N=int(input())
a= list(map(int, input().split()))
a.sort()
b=[None]*N
b[0]=a[0]
A=0
for i in range(1,N):
  b[1]=a[i]
  for j in range(2,N):
    b[j]=b[j-1]^b[j-2]
    if b[j] not in a:
      break
  else:
    b.sort()
    if a==b:
      A=1
      break
if A==1:
  print("Yes")
else:
  print("No")


### FIXED CODE ###

N=int(input())
a=list(map(int,input().split()))
t=0
for i in a:
    t=t^i
print("No" if t else "Yes")
### BUGGY CODE ###

#!/usr/bin/env python3
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections
from decimal import Decimal # 10進数で考慮できる

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))


N = int(input())

for n in range(1, N + 1):
    ans = 0
    for z in range(1, int(n ** 0.5)):
        for y in range(1, int((n - z ** 2) ** 0.5)):
            for x in range(1, int((n - z**2 - y**2)**0.5)):
                if x**2 + y**2 + z ** 2 + x*y + y*z + x*z == n:
                    ans += 1
    print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections
from decimal import Decimal # 10進数で考慮できる

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))


N = int(input())

anss = [0 for i in range(N + 1)]
for x in range(1, int(math.sqrt(N))):
    for y in range(1, int(math.sqrt(N))):
        for z in range(1, int(math.sqrt(N))):
            tmp = x ** 2 + y ** 2 + z ** 2 + x*y + x*z + y*z
            if tmp <= N:
                anss[tmp] += 1 

for i in range(1, N + 1):
    print(anss[i])
### BUGGY CODE ###

N=int(input())
a=[]
x=0
for i in range(N):

    h=list(input())

    h.sort(reverse=False)
    
    a.append(h)


for j in range(N):

    if len(a)==0:
        break
    
    x+=sum(range(a.count(a[0])))
    y=a[0]

    if a.count(y)>=1:

        for k in range(a.count(y)):

            a.remove(y)
            
    

print(x)


### FIXED CODE ###

N=int(input())

H=[]
c=0
t=0
for i in range(N):
    h=list(input())
    h.sort(reverse=False)
    H.append(h)

H.sort(reverse=False)

for j in range(N-1):
    
    if H[j]==H[j+1]:
        c+=1

    else:
        t+=int((c)*(c+1)/2)
        c=0

if c:
    t+=int(((c)*(c+1)/2))
        

print(t)
### BUGGY CODE ###

K = int(input())

def gcd(x,y):
	while y:
		x,y = y, x % y
	return x

ret = 0
for i in range(1,K+1):
	for j in range(1,K+1):
		for k in range(1,K+1):
			ret = ret + gcd(i,gcd(j,k))

print(ret)

### FIXED CODE ###

K = int(input())

def gcd(x,y):
	while y:
		x,y = y, x % y
	return x

ret = 0
for i in range(1,K+1):
	for j in range(1,K+1):
		for k in range(1,K+1):
			ret = ret + gcd(i,gcd(j,k))

print(ret)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def main():
    n = int(input())
    a = list(map(int, input().split()))
    ans = [float('inf')] * n
    for i in range(1, n):
        ans[i] = abs(sum(a[:i])-sum(a[i:]))

    print(min(ans))


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def main():
    n = int(input())
    a = list(map(int, input().split()))
    s = sum(a)
    t = [0] * n
    for i in range(n-1):
        t[i+1] = t[i] + a[i]
    print(min(abs(s-2*t[i]) for i in range(1, n)))


if __name__ == '__main__':
    main()
### BUGGY CODE ###

n=int(input())
ans=0
hoge=[]
for i in range(n):
  a=list(input())
  a.sort()
  if(hoge.count(a)==0):
    hoge.append(a)
  else:
    ans+=hoge.count(a)
    hoge.append(a)
print(ans)

### FIXED CODE ###

n=int(input())
dic={}
for i in range(n):
  hoge=list(input())
  hoge.sort()
  hoge=str(hoge)
  if(hoge in dic):
    dic[hoge]+=1
  else:
    dic[hoge]=1


ans=0
for i in dic.values():
  ans+=i*(i-1)//2
print(ans)
### BUGGY CODE ###

# Author: cr4zjh0bp
# Created: Tue Mar 17 19:50:06 UTC 2020
import sys
 
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

sys.setrecursionlimit(10 ** 6)

n, q = na()
ab = nan(n - 1)
px = nan(q)

tree = [[] for _ in range(n)]
for i in range(n - 1):
    a, b = ab[i]
    a -= 1
    b -= 1
    tree[a].append(b)
    tree[b].append(a)

cnt = [0 for _ in range(n)]
for i in range(q):
    p, x = px[i]
    p -= 1
    cnt[p] += x

def dfs(i, p, s):
    x = s + cnt[i]
    cnt[i] = x
    for j in tree[i]:
        if j == p:
            continue
        dfs(j, i, x)

dfs(0, -1, 0)
print(*cnt)

### FIXED CODE ###

# Author: cr4zjh0bp
# Created: Tue Mar 17 19:50:06 UTC 2020
import sys
 
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

from collections import deque

sys.setrecursionlimit(10 ** 6)

n, q = na()
ab = nan(n - 1)
px = nan(q)

tree = [[] for _ in range(n)]
for i in range(n - 1):
    a, b = ab[i]
    a -= 1
    b -= 1
    tree[a].append(b)
    tree[b].append(a)

cnt = [0 for _ in range(n)]
for i in range(q):
    p, x = px[i]
    p -= 1
    cnt[p] += x

def dfs(i, p, s):
    x = s + cnt[i]
    cnt[i] = x
    for j in tree[i]:
        if j == p:
            continue
        dfs(j, i, x)

def bfs():
    q = deque()
    q.append((0, -1, 0))
    while len(q):
        p, b, s = q.popleft()
        x = s + cnt[p]
        cnt[p] = x
        for i in tree[p]:
            if i == b:
                continue
            q.append((i, p, x))

bfs()
print(*cnt)
### BUGGY CODE ###

s=input()
l=len(s)
k=int(input())
x=set()
for i in range(1,l+1):
    for j in range(l-i+1):
        x.add(s[j:j+i])
x=sorted(list(x))
print(x[k-1])


### FIXED CODE ###

s=input()
l=len(s)
k=int(input())
x=set()
for i in range(1,min(l,k)+1):
    for j in range(l-i+1):
        x.add(s[j:j+i])
x=sorted(list(x))
print(x[k-1])
### BUGGY CODE ###

cnt = 0
R, G, B, N = map(int, input().split())
comb = []
tmp = []
rgb = [R, G, B]

for r in range((N//R)+2):
    for g in range((N//G)+2):
        m = N - r*R - g*G
        if m == 0 or (m % B == 0 and m >= B):
            cnt += 1

print(cnt)

### FIXED CODE ###

cnt = 0
R, G, B, N = map(int, input().split())
comb = []
tmp = []
rgb = [R, G, B]

for r in range((N//R)+2):
    for g in range((N//G)+2):
        m = N - r*R - g*G
        if m == 0 or (m % B == 0 and m >= B):
            cnt += 1

print(cnt)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
n,q=map(int,input().split())
s=input().rstrip()
td=[]
for _ in range(q):
	t,d=input().split()
	td.append((t,d))
l=-1;r=n+1
while r-l>1:#l以上r未満
	mid=(l+r)//2
	now=mid
	if not 0<=now<n:
		if now==-1:
			l=mid
		else:
			r=mid
		continue
	for i in range(q):
		if s[now]==td[i][0]:
			if td[i][1]=="L":
				now-=1
			else:
				now+=1
		if not 0<=now<n:
			f=0
			break
	if now==-1:
		l=mid
	else:
		r=mid
Left=l
l=-2;r=n
while r-l>1:#l over r以下
	mid=(l+r)//2
	now=mid
	if not 0<=now<n:
		if now==n:
			r=mid
		else:
			l=mid
		continue
	for i in range(q):
		if s[now]==td[i][0]:
			if td[i][1]=="L":
				now-=1
			else:
				now+=1
		if not 0<=now<n:
			f=0
			break
	if now==n:
		r=mid
	else:
		l=mid
Right=r#Right,Leftはどこまで排除されるか
print(Right-Left-1)

### FIXED CODE ###

import sys
input=sys.stdin.readline
n,q=map(int,input().split())
s=input().rstrip()
td=[]
for _ in range(q):
	t,d=input().split()
	td.append((t,d))
l=-1;r=n+1
while r-l>1:#l以上r未満
	mid=(l+r)//2
	now=mid
	if not 0<=now<n:
		if now==-1:
			l=mid
		else:
			r=mid
		continue
	for i in range(q):
		if s[now]==td[i][0]:
			if td[i][1]=="L":
				now-=1
			else:
				now+=1
		if not 0<=now<n:
			f=0
			break
	if now==-1:
		l=mid
	else:
		r=mid
Left=l
l=-2;r=n
while r-l>1:#l over r以下
	mid=(l+r)//2
	now=mid
	if not 0<=now<n:
		if now==n:
			r=mid
		else:
			l=mid
		continue
	for i in range(q):
		if s[now]==td[i][0]:
			if td[i][1]=="L":
				now-=1
			else:
				now+=1
		if not 0<=now<n:
			f=0
			break
	if now==n:
		r=mid
	else:
		l=mid
Right=r#Right,Leftはどこまで排除されるか
print(Right-Left-1)
### BUGGY CODE ###

import numpy as np
import sys
def input():
    return sys.stdin.readline()[:-1]

N, K, Q = map(int, input().split())

points = np.array([K for _ in range(N)])

for q in range(Q):
    A = int(input()) - 1
    points -= 1
    points[A] +=1
    # points = [p if i == A else p-1 for i, p in enumerate(points)]

for p in points:
    if p < 1:
        print('No')
    else:
        print('Yes')


### FIXED CODE ###

import numpy as np
import sys
def input():
    return sys.stdin.readline()[:-1]

N, K, Q = map(int, input().split())

points = np.array([K - Q for _ in range(N)])

for q in range(Q):
    A = int(input()) - 1
    points[A] +=1

for p in points:
    if p < 1:
        print('No')
    else:
        print('Yes')
### BUGGY CODE ###

import math

def P(n, r):
    return math.factorial(n)//math.factorial(n-r)
def C(n, r):
    return P(n, r)//math.factorial(r)

N = int(input())
A = list(map(int, input().split()))

dic = {}
for i in range(N):
  if A[i] in dic:
    dic[A[i]] += 1
  else:
    dic[A[i]] = 1

memo = {}
ans = 0
for k in dic:
  tmp  =dic[k]
  if tmp >= 2:
    memo[k] = C(tmp, 2)
    ans += memo[k]

for i in range(N):
  tmp = dic[A[i]]
  if tmp == 1:
    print(ans)
  elif tmp == 2:
    print(ans - 1)
  else:
    print(ans - (memo[A[i]] - C(tmp-1, 2)))


### FIXED CODE ###

import math

N = int(input())
A = list(map(int, input().split()))

dic = {}
for i in range(N):
  if A[i] in dic:
    dic[A[i]] += 1
  else:
    dic[A[i]] = 1

memo = [0 for i in range(10 ** 6)]
ans = 0
for k in dic:
  tmp  =dic[k]
  if tmp >= 2:
    if memo[tmp] == 0:
      memo[tmp] = tmp * (tmp - 1) // 2
      ans += memo[tmp]
    else:
      ans += memo[tmp]

for i in range(N):
  tmp = dic[A[i]]
  if tmp == 1:
    print(ans)
  elif tmp == 2:
    print(ans - 1)
  else:
    print(ans - tmp * (tmp - 1) // 2 + (tmp - 1) * (tmp - 2) // 2)
### BUGGY CODE ###

S=input()
while "SSTT" in S:
    S=S.replace("SSTT","")
while "ST" in S:
    S=S.replace("ST","")
print(len(S))

### FIXED CODE ###

from collections import deque
S=list(map(lambda x: 1 if x=="T" else 0,input()))

q=deque()

for i in S:

    if i:
        if (not q) or q[-1]!=0:
            q.append(i)
        elif q and q[-1]==0:
            q.pop()
    else:
        q.append(i)
print(len(q))
### BUGGY CODE ###

x,y=map(int,input().split())
if x//y>=1 and x%y==0:
    print(-1)
    exit()
t=2
p=100000000000000000
while 1:
    if x*t>p:
        break
    elif x*t%y:
        print(x*t)
        exit()
print(-1)


### FIXED CODE ###

x,y=map(int,input().split())
if x//y>=1 and x%y==0:
    print(-1)
    exit()
a=x*(y-1)
b=x*(y+1)
t=1000000000000000000
if a>0 and a%y and a<=t:
    print(a)
elif b>0 and b%y and b<=t:
    print(b)
else:
    print(-1)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)

def main():
    N,K = map(int,input().split())
    p = 10**9+7

    dp = [0] * (K+1)
    ans = 0
    for i in reversed(range(K)):
        dp[i+1] = (K//(i+1)) ** N
        max = K//(i+1)
        if max > 1:
            for j in range(2,max+1):
                dp[i+1] -= dp[(i+1)*j]

        ans += (dp[i+1] * (i+1)) % p

    print(ans % p)


if __name__ == "__main__":
  main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))


INF=10**20
def main():
    N,K=mi()
    MOD = 10**9+7

    ans = 0
    dic = {} 
    for x in range(K,0,-1):  # gcd = x となるA1~AN(<=K)を探す
        p_count = K//x
        count = pow(p_count,N,MOD)

        i = 2
        while x*i <= K:
            if not x*i in dic: break
            count -= dic[x*i]
            count %= MOD
            i += 1

        count %= MOD
        dic[x] = count
        
        ans += count * x
        ans %= MOD
        # print(x,count)
    
    print(ans)








if __name__ == "__main__":
    main()
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))

ans = 0

for i in range(2**n):
    tmp = []
    for j in range(n):
        if ((i >> j) & 1):
            tmp .append(a[j])
    tmp.sort()
    if len(tmp) == 3 and abs(tmp[0]-tmp[1]) < tmp[2] and tmp[2] < tmp[0]+tmp[1] and tmp[0] != tmp[1] != tmp[2]:
        ans += 1

print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))

ans = 0

for i in range(n):
    for j in range(1,n):
        for k in range(2,n):
            tmp = []
            if i != j != k and i < j < k:
                tmp.append(a[i])
                tmp.append(a[j])
                tmp.append(a[k])
                tmp.sort()
                if len(tmp) == 3 and abs(tmp[0]-tmp[1]) < tmp[2] and tmp[2] < tmp[0]+tmp[1] and tmp[0] != tmp[1] != tmp[2]:
                    ans += 1

print(ans)
### BUGGY CODE ###

N, S = map(int, input().split())
A = list(map(int, input().split()))
mod = 998244353
dp = [[0 for j in range(S + 1)] for i in range(N + 1)]
dp[0][0] = 1
for i in range(N):
    for j in range(S + 1):
        dp[i + 1][j] += 2 * dp[i][j]
        dp[i + 1][j] %= mod
        if j + A[i] <= S:
            dp[i + 1][j + A[i]] += dp[i][j]
            dp[i + 1][j + A[i]] %= mod
print(dp[N][S])


### FIXED CODE ###

N, S = map(int, input().split())
A = list(map(int, input().split()))
mod = 998244353
dp = [[0 for j in range(S + 1)] for i in range(N + 1)]
dp[0][0] = 1
for i in range(N):
    for j in range(S + 1):
        dp[i + 1][j] += 2 * dp[i][j]
        dp[i + 1][j] %= mod
        if j + A[i] <= S:
            dp[i + 1][j + A[i]] += dp[i][j]
            dp[i + 1][j + A[i]] %= mod
print(dp[N][S])