Harryxun/stf_run huggingface dataset:
from collections import defaultdict
from collections import deque
from collections import Counter
import math
import itertools

def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()

class UnionFind():
	def __init__(self, n):
		self.n = n
		self.parents = [-1] * n

	def find(self, x):
		if self.parents[x] < 0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)

		if x == y:
			return

		if self.parents[x] > self.parents[y]:
			x, y = y, x

		self.parents[x] += self.parents[y]
		self.parents[y] = x

	def size(self, x):
		return -self.parents[self.find(x)]

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def members(self, x):
		root = self.find(x)
		return [i for i in range(self.n) if self.find(i) == root]

	def roots(self):
		return [i for i, x in enumerate(self.parents) if x < 0]

	def group_count(self):
		return len(self.roots())

	def all_group_members(self):
		return {r: self.members(r) for r in self.roots()}

	def __str__(self):
		return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

n,m = readInts()
u = UnionFind(n-1)
for i in range(m):
	a,b = readInts()
	u.union(a-1,b-1)

print(u.group_count())

### FIXED CODE ###

from collections import defaultdict
from collections import deque
from collections import Counter
import math
import itertools

def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()

class UnionFind():
	def __init__(self, n):
		self.n = n
		self.parents = [-1] * n

	def find(self, x):
		if self.parents[x] < 0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)

		if x == y:
			return

		if self.parents[x] > self.parents[y]:
			x, y = y, x

		self.parents[x] += self.parents[y]
		self.parents[y] = x

	def size(self, x):
		return -self.parents[self.find(x)]

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def members(self, x):
		root = self.find(x)
		return [i for i in range(self.n) if self.find(i) == root]

	def roots(self):
		return [i for i, x in enumerate(self.parents) if x < 0]

	def group_count(self):
		return len(self.roots())

	def all_group_members(self):
		return {r: self.members(r) for r in self.roots()}

	def __str__(self):
		return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

n,m = readInts()
u = UnionFind(n)
for i in range(m):
	a,b = readInts()
	u.union(a-1,b-1)

print(u.group_count()-1)
K,X = map(int,input().split())
A = []
for i in range(X-(K-1),X+(K-1)+1):
  A.append(i)
print(" ".join(A[0]))

### FIXED CODE ###

K,X = map(int,input().split())
A = []
for i in range(X-(K-1),X+(K-1)+1):
  A.append(i)
print(*A)
n=int(input())
arr=list(map(int,input().split()))
ans=[0]*100000
for i in range(n):
    ans[arr[i]]+=1
sm=sum(arr)
q=int(input())
for i in range(q):
    x,y=(map(int,input().split()))
    sm=sm-(x*ans[x])
    sm=sm+(y*ans[x])
    ans[y]+=ans[x]
    ans[x]=0
    print(sm)


### FIXED CODE ###

from collections import Counter
n=int(input())
arr=list(map(int,input().split()))
ans=Counter(arr)
sm=sum(arr)
q=int(input())
for i in range(q):
    x,y=(map(int,input().split()))
    sm=sm-(x*ans[x])
    sm=sm+(y*ans[x])
    ans[y]+=ans[x]
    ans[x]=0
    print(sm)
n,a,b=map(int, input().split())
s=list(input())
num=0
qual=[]
s_b=[i for i,x in enumerate(s) if x=='b']
for i in range(n):
  if num<a+b:
    if s[i]=='c':
      qual.append('No')
    elif s[i]=='a':
      num+=1
      qual.append('Yes')     
    else:
      if s_b.index(i)<b:
        num+=1
        qual.append('Yes')
      else:
        qual.append('No')   
  else:
    qual.append('No')
print(qual, split='\n')

### FIXED CODE ###

n,a,b=map(int, input().split())
s=list(input())
num=0
num_f=0
qual=[]
for i in range(n):
  if num<a+b:
    if s[i]=='a':
      num+=1
      qual.append('Yes')     
    elif s[i]=='b' and num_f<b:
      num+=1
      num_f+=1
      qual.append('Yes')
    else:
      qual.append('No')   
  else:
    qual.append('No')
for i in range(n):
  print(qual[i])
int_s = input()
str_sr = int_s[::-1]


str_a = ['dream', 'dreamer', 'erase', 'eraser']

str_r = list(map(lambda x: x[::-1], str_a))

result = True

while len(str_sr):
    currnt_flg = False
    for r in str_r:
        print('r:' + r)
        if len(str_sr) >= len(r) and str_sr[:len(r)] == r:
            print('ok')
            str_sr = str_sr[len(r):]
            print(str_sr)
            current_flg = True
            break
    else:
        result = False
        break

if result:
    print('YES')
else:
    print('No')

### FIXED CODE ###

int_s = input()
str_sr = int_s[::-1]


str_a = ['dream', 'dreamer', 'erase', 'eraser']

str_r = list(map(lambda x: x[::-1], str_a))

result = True

while len(str_sr):
    currnt_flg = False
    for r in str_r:
        # print('r:' + r)
        if len(str_sr) >= len(r) and str_sr[:len(r)] == r:
            # print('ok')
            str_sr = str_sr[len(r):]
            # print(str_sr)
            current_flg = True
            break
    else:
        result = False
        break

if result:
    print('YES')
else:
    print('NO')
import collections
N=int(input())
S=[input() for i in range(N)]
c=collections.Counter(S)
most=c.most_common()[0][1]
if len(c)==1:
  print(c.most_common()[0][0])
else:
  for i in range(len(c)):
    print(c.most_common()[i][0])
    if c.most_common()[i+1][1] !=most:
      break


### FIXED CODE ###

import collections
N = int(input())
s = [input() for i in range(N)]
 
counter = collections.Counter(s)
count = counter.most_common()
 
most = count[0][1]
 
c =[]
for i in range(len(count)):
    if count[i][1] == most:
        c.append(count[i][0])
 
c.sort()
 
for i in range(len(c)):
    print(c[i])
a = int(input())

b = []

for i in a:
    b.append(list(input().split())

res = 0

for i in b:
    if (i[1] == 'BTC'):
        res += i[0]*380000
    else:
        res += i[0]

print(res) 

### FIXED CODE ###

a = int(input())

b = []

for i in range(a):
    b.append(input().split())

res = 0

for i in b:
    if (i[1] == 'BTC'):
        res += float(i[0])*380000
    else:
        res += int(i[0])

print(res)
X, N = map(int, input().split())
if N == 0:
  print(X)
  exit()
elif N == 100:
  if X <= 50:
    print(-1)
  else:
    print(101)
else:
  p = set(map(int, input().split()))

l = 100
d = 0
for i in range(100):
  if i+1 not in p:
    li = abs(X-i-1)
    if li < l:
      l = li
      d = i+1
    elif li >= l:
      break
print(d)

### FIXED CODE ###

X, N = map(int, input().split())
if X <= 50:
  l = X
  d = 0
else:
  l = 101 - X
  d = 101

if N == 0:
  print(X)
  exit()
elif N == 100:
  print(d)
  exit()
else:
  p = set(map(int, input().split()))

for i in range(100):
  if i+1 not in p:
    li = abs(X-i-1)
    if li < l:
      l = li
      d = i+1
    elif li == l:
      if i+1 < d:
        d = i+1
    elif li > l:
      break
print(d)
s,t=input(),input()
rs=rt=[""for _ in range(26)]
def a(n):return [chr(ord('a')+i)for i in range(26)].index(n)
for i in range(len(s)):
  if rs[a(s[i])]=="":rs[a(s[i])]=t[i]
  elif rs[a(s[i])]!=t[i]:print("No");exit()
  if rt[a(t[i])]=="":rt[a(t[i])]=s[i]
  elif rt[a(t[i])]!=s[i]:print("No");exit()
rint("Yes")

### FIXED CODE ###

s,t=input(),input()
rs=[""for _ in range(26)]
rt=[""for _ in range(26)]
def a(n):return [chr(ord('a')+i)for i in range(26)].index(n)
for i in range(len(s)):
  ss,tt=a(s[i]),a(t[i])
  if rs[ss]=="":rs[ss]=t[i]
  elif rs[ss]!=t[i]:print("No");exit()
  if rt[tt]=="":rt[tt]=s[i]
  elif rt[tt]!=s[i]:print("No");exit()
print("Yes")
class unionFind:
    parent = []
    count = 0

    def __init__(self, N):
        self.parent = [i for i in range(N)]
        self.count = N
        self.nums = [1]*N

    def root(self, x):
        if self.parent[x] == x:
            return(x)
        else:
            self.parent[x] = self.root(self.parent[x])
            return(self.parent[x])

    def same(self, x, y):
        x, y = x-1, y-1
        return(self.root(x) == self.root(y))

    def unite(self, x, y):
        x, y = x-1, y-1
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        else:
            self.count -= 1
            self.parent[x] = y
            self.nums[y] += self.nums[x]
            self.nums[x] = 0
            return


N, M = map(int, input().split())
G = unionFind(N)
ans = [0]*M
ab = [tuple(map(int, input().split())) for i in range(M)]

tmp = (N * (N-1)) // 2
for i, x in enumerate(reversed(ab)):
    a, b = x[0], x[1]
    ans[M-1-i] = tmp
    if G.same(a, b):
        continue
    else:
        tmp -= G.nums[a-1] * G.nums[b-1]
        G.unite(a, b)


for i in range(M):
    print(ans[i])


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**5)


class unionFind:
    parent = []
    nums = []

    def __init__(self, n):
        self.parent = [i for i in range(n)]
        self.nums = [1]*n

    def root(self, x):
        if self.parent[x] == x:
            return(x)
        else:
            self.parent[x] = self.root(self.parent[x])
            return(self.parent[x])

    def same(self, x, y):
        x, y = x-1, y-1
        return(self.root(x) == self.root(y))

    def unite(self, x, y):
        x, y = x-1, y-1
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        else:
            self.parent[x] = y
            self.nums[y] += self.nums[x]
            self.nums[x] = 0
            return


N, M = map(int, input().split())
G = unionFind(N)
ans = [0]*M
ab = [tuple(map(int, input().split())) for i in range(M)]

tmp = (N * (N-1)) // 2
for i, x in enumerate(reversed(ab)):
    a, b = x[0], x[1]
    ans[M-1-i] = tmp
    a = G.root(a-1)
    b = G.root(b-1)
    if a == b:
        continue
    else:
        tmp -= G.nums[a] * G.nums[b]
        G.parent[a] = b
        G.nums[b] += G.nums[a]
        G.nums[a] = 0


for i in range(M):
    print(ans[i])
# https://beta.atcoder.jp/contests/abc099/tasks/abc099_a
# A - ABD

# A_ABD.py

N = int(input())

C_or_D = (N-1) // 999


name = ""

if C_or_D == 0:
    name += "ABC"
    #n = N
elif C_or_D == 1:
    name += "ABD"
    #n = '{0:03d}'.format(N - 999)

name += str(n)

print(name)


### FIXED CODE ###

# https://beta.atcoder.jp/contests/abc099/tasks/abc099_a
# A - ABD

# A_ABD.py

N = int(input())

C_or_D = (N-1) // 999


name = ""

if C_or_D == 0:
    name += "ABC"
    #n = N
elif C_or_D == 1:
    name += "ABD"
    #n = '{0:03d}'.format(N - 999)

#ame += str(n)

print(name)
# coding: utf-8

import sys

lines = sys.stdin.readlines()

n,a,b,c = lines
n = int(n.strip('\n'))
a = str(a.strip('\n'))
b = str(b.strip('\n'))
c = str(c.strip('\n'))

num = 0
if not(n == a == b == c):
  for i in range(n):
    if not(a[i] == b[i] == c[i]):
      if a[i] == b[i] or b[i] == c[i] or c[i] == a[i]:
        num = num+1
      else:
        num = num+2

print(num)       

sys.exit(0)


### FIXED CODE ###

# coding: utf-8

import sys
import math

args = input().split()

n = int(args[0])
a = int(args[1])
b = int(args[2])

reta = a
retb = (n - a) - b

if retb > 0:
  retb = 0
else:
  retb = abs(retb)

print('{reta} {retb}'.format(reta=min(a,b),retb=retb))

sys.exit(0)
var str = readLine()!

if str=="ABC"{
  print("ARC")
}else{
  print("ABC")
}

### FIXED CODE ###

s=input()

if s=='ABC':
    ans='ARC'
else:
    ans='ABC'
print(ans)
n = int(input())
l2 = list(map(int, input().split()))

from collections import Counter
c = Counter(l2)
k = list(c.keys())
k.sort()

from bisect import bisect_left, bisect_right
l2.sort()

ans = 0
for i in range(len(k)):
    for j in range(i+1, len(k)):
        c_min = k[j] - k[i]
        c_max = k[i] + k[j]

        idx = bisect_right(l2, k[j])
        tmp = l2[idx:]

        idx_min = bisect_right(tmp, c_min)
        idx_max = bisect_left(tmp, c_max)

        ans += max(0, idx_max - idx_min) * c[k[i]] * c[k[j]]

for _k in k:
    if c[_k] >= 2:
        idx = bisect_right(l2, _k)
        tmp = l2[idx:]
        idx_min = bisect_right(tmp, 0)
        idx_max = bisect_left(tmp, _k * 2)

        ans += max(0, idx_max - idx_min) * (c[_k] - 1) * c[k] // 2

print(ans)


### FIXED CODE ###

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

l.sort()
from bisect import bisect_left
ans = 0
for i in range(n):
    for j in range(i):
        idx = bisect_left(l, l[i] + l[j])
        ans += idx - i - 1
print(ans)
n=int(input())
a=list(map(int,input().split()))
q=int(input())
sum=sum(a)
a2,a3=[],[]
import bisect as bs

for i in set(a):
    a2.append(i)
    a3.append(a.count(i))

for i in range(q):
    b,c=map(int,input().split())
    if b in a2 and c in a2:
        b_idx=bs.bisect_left(a2,b)
        c_idx=bs.bisect_left(a2,c)
        sum+=(c-b)*a3[b_idx]
        a3[c_idx]+=a3[b_idx]
        a3[b_idx]=0
    elif b in a2:
        a2.append(c)
        a3.append(0)
        b_idx=bs.bisect_left(a2,b)
        sum+=(c-b)*a3[b_idx]
        a3[-1]+=a3[b_idx]
        a3[b_idx]=0
    print(sum)

### FIXED CODE ###

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

count=[0]*(10**5+1)

for i in a:
    count[i]+=1

for i in range(q):
    b,c=map(int,input().split())
    if count[b]!=0:
        sum+=(c-b)*count[b]
        count[c]+=count[b]
        count[b]=0
    print(sum)
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys

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

S = str(input())

def check(T,S):
    if T == S:
        return 1
    adds = ["dream","dreamer","erase","eraser"]
    for i,add in enumerate(adds):
        if S[len(T):len(T)+len(add)] == add:
            if check(T+add,S) == 1:
                return 1

if check("",S):
    print("YES")
else:
    print("NO")


### FIXED CODE ###

# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys

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

S = str(input())
S = list(S)
S.reverse()
S = "".join(S)

def check(T):
    if len(S) == 0:
        return 1
    adds = ["maerd","remaerd","esare","resare"]
    q = copy.deepcopy(adds)
    while len(q) > 0:
        t = q.pop()
        if t == S:
            return 1
        for add in adds:
            if S[len(t):len(t+add)] == add:
                q.append(t+add)
    return 0

if check(""):
    print("YES")
else:
    print("NO")
H, W =  map(int, input().split())

S = []
for _ in range(H):
    tmp = list(input())
    S.append(tmp)
    
import numpy as np

def count_light(Gs, h, w):
    Gc = np.empty((h,w))
    for i, gs in enumerate(Gs):
        count = 0
        for j, s in enumerate(gs):
            if s == '#':
                count = 0
                Gc[i][j] = 0
            else:
                count += 1
                Gc[i][j] = count

    return Gc

Gs1 = np.asarray(S)
Gn1 = count_light(Gs1, H, W)

Gs2 = np.rot90(Gs, k=1)
Gn2 = count_light(Gs2, W, H)

Gs3 = np.rot90(Gs2, k=1)
Gn3 = count_light(Gs3, H, W)

Gs4 = np.rot90(Gs3, k=1)
Gn4 = count_light(Gs4, W, H)

Gn2 = np.rot90(Gn2, k=-1)
Gn3 = np.rot90(Gn3, k=-2)
Gn4 = np.rot90(Gn4, k=-3)

Gsum = Gn1+Gn2+Gn3+Gn4
ans = int(np.max(Gsum)-3)
print(ans)


### FIXED CODE ###

H, W =  map(int, input().split())

S = []
for _ in range(H):
    tmp = list(input())
    S.append(tmp)
    
import numpy as np

def count_light(Gs, h, w):
    Gc = np.empty((h,w))
    for i in range(w):
        if i == 0:
            Gc[:, i] = Gs[:, i]
        else:
            Gc[:, i] = (Gc[:, i-1] + 1) * Gs[:, i]

    return Gc

Gs1 = np.asarray(S) == "."
Gn1 = count_light(Gs1, H, W)

Gs2 = np.rot90(Gs1, k=1)
Gn2 = count_light(Gs2, W, H)

Gs3 = np.rot90(Gs2, k=1)
Gn3 = count_light(Gs3, H, W)

Gs4 = np.rot90(Gs3, k=1)
Gn4 = count_light(Gs4, W, H)

Gn2 = np.rot90(Gn2, k=-1)
Gn3 = np.rot90(Gn3, k=-2)
Gn4 = np.rot90(Gn4, k=-3)

Gsum = Gn1+Gn2+Gn3+Gn4
ans = int(np.max(Gsum)-3)
print(ans)
S=input()
T=input()
cnt=[]
for i in range(len(S)-len(T)):
    count=0
    kari=S[i:i+len(T)]
    for j in range(len(T)):
        if kari[j]!=T[j]:
            count+=1
    cnt.append(count)
print(min(cnt))

### FIXED CODE ###

S=input()
T=input()
cnt=[]
if len(S)==len(T):
    kazu=0
    for i in range(len(S)):
        if S[i]!=T[i]:
            kazu+=1
    cnt.append(kazu)


for i in range(len(S)-len(T)):
    count=0
    kari=S[i:i+len(T)]
    for j in range(len(T)):
        if kari[j]!=T[j]:
            count+=1
    cnt.append(count)
print(min(cnt))
n = int(input())
s = input()
cnt = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        if s[i] != s[j]:
            if (s[i]+s[j]).count('R') == 0:
                cnt += s[j+1:n].count('R')
                if s[j+i] == 'R' and j-i > n-j:
                    cnt -= 1
            elif (s[i]+s[j]).count('G') == 0:
                cnt += s[j+1:n].count('G')
                if s[j+i] == 'G' and j-i > n-j:
                    cnt -= 1
            else:
                cnt += s[j+1:n].count('B')
                if s[j+i] == 'B' and j-i > n-j:
                    cnt -= 1
print(cnt)

### FIXED CODE ###

n = int(input())
s = input()
cnt = s.count('R')*s.count('G')*s.count('B')
for i in range(n-2):
    for j in range(i+1,n-1):
        if s[i] != s[j]:
            if 2*j-i > n-1:
                break
            if s[2*j-i] not in(s[i],s[j]):
                cnt -= 1
print(cnt)
N, K = map(int, input().split())
A = sorted(list(map(int, input().split())))


if K > A[-1]:
    print('IMPOSSIBLE')
else:
    flag = True
    for i in range(N - 1):
        if A[i] % (A[i + 1] - A[i]) == 0 or \
           (A[i + 1] - A[i]) % A[i] == 0 or \
           A[i + 1] % (A[i + 1] - A[i]) == 0:
            flag = False
            break
    if flag:
        print("POSSIBLE")
    else:
        print('IMPOSSIBLE')


### FIXED CODE ###


from fractions import gcd


N, K = map(int, raw_input().split())
A = sorted(list(map(int, raw_input().split())))


if K > A[-1]:
    print('IMPOSSIBLE')
else:
    flag = True
    tmp = reduce(gcd, A)
    if tmp != 1:
        flag = False
    for a in A:
        if a == K or (K - a) % tmp == 0:
            flag = True
            break
    if flag:
        print("POSSIBLE")
    else:
        print('IMPOSSIBLE')
n = long(input())
l0 = 2L
l1 = 1L
if n == 0:
    print(l0)
if n == 1:
    print(l1)

l_prev = l0
l_next = l1

l_new = 0L
for i in range(2, n+1):
    l_new = l_prev + l_next
    l_prev = l_next
    l_next = l_new
print(l_new)


### FIXED CODE ###

n = int(input())

l = [2, 1]
for i in range(2, n+1):
    l.append(l[i - 2] + l[i - 1])
print(l[n])
import sys
def gcd(a, b):
    for i in range(1, a):
        if a % i == 0:
            t = a // i
            if b % t == 0:
                return t
for line in sys.stdin:
    a, b = sorted(map(int, line.split()))
    gcdab = gcd(a, b)
    print(gcdab, a // gcdab * b)

### FIXED CODE ###

import sys
def gcd(a, b):
    for i in range(1, a+1):
        if a % i == 0:
            t = a // i
            if b % t == 0:
                return t
for line in sys.stdin:
    a, b = sorted(map(int, line.split()))
    gcdab = gcd(a, b)
    print(gcdab, a // gcdab * b)
print(input().split().index("0") + 1)


### FIXED CODE ###

print(input()[:3])
w, h = input('')
print(w*h)


### FIXED CODE ###

w,h = map(int, raw_input().split())

print(str(w*h) + ' ' + str((w+h)*2))
n = int(input())
lis = list(map(int, input().split())
sum = 0
for i in lis:
   for j in lis:
        sum += i * j
print(sum % 1000000009)           

### FIXED CODE ###

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

s = sum(lis) ** 2
ss = sum([i ** 2 for i in lis])

print(((s - ss)//2)%(10**9+7))
#!/usr/bin/env python3

import heapq
import sys
input=sys.stdin.readline

t=int(input())
for _ in range(t):
    n=int(input())
    arr=[list(map(int,input().split())) for _ in range(n)]
    head=[]
    tail=[]
    for k,l,r in arr:
        if l>=r or k==n:
            head.append((k,l,r))
        else:
            tail.append((k,l,r))
    head=sorted(head,key=lambda x:x[0])
    q=[]
    cnt=0
    ans=[]
    for k,l,r in head:
        heapq.heappush(q,(l-r,l))
        cnt+=1
        while cnt>k:
            tmp,val=heapq.heappop(q)
            ans.append((tmp,val-tmp))
            cnt-=1
    ans+=list(q)
    cnt=len(ans)
    tail2=[]
    for k,l,r in tail:
        if k<=cnt:
            ans.append((l-r,r))
        else:
            tail2.append((k,l,r))
    tail2=sorted(tail2,reverse=True,key=lambda x:x[0])
    q2=[]
    cnt2=0
    for k,l,r in tail2:
        heapq.heappush(q2,(r-l,r))
        cnt2+=1
        while cnt2>(n-k+1):
            tmp,val=heapq.heappop(q2)
            ans.append((tmp,val-tmp))
            cnt-=1
    ans+=list(q2)
    ret=0
    for _,val in ans:
        ret+=val
    print(ret)

### FIXED CODE ###

#!/usr/bin/env python3

import heapq
import sys
input=sys.stdin.readline

t=int(input())
for _ in range(t):
    n=int(input())
    arr=[list(map(int,input().split())) for _ in range(n)]
    q=[]
    ans=0
    camels1=[[] for _ in range(n+1)]
    camels2=[[] for _ in range(n+1)]
    for k,l,r in arr:
        ans+=min(l,r)
        if l>=r:
            camels1[k].append((l,r))
        else:
            camels2[k].append((l,r))
    for i in range(1,n+1):
        for l,r in camels1[i]:
            heapq.heappush(q,l-r)
        while len(q)>i:
            heapq.heappop(q)
    while len(q)!=0:
        ans+=heapq.heappop(q)
    for i in range(n,0,-1):
        for l,r in camels2[i]:
            heapq.heappush(q,r-l)
        while len(q)>(n-i):
            heapq.heappop(q)
    while len(q)!=0:
        ans+=heapq.heappop(q)
    print(ans)
S = input()
#print(len(S))
dire = ['dream','dreamer','erase','eraser']
flag = 0
i=0
j=0

while True:

    tmp = dire[j]
    ind = i

    if ind + len(dire[j]) <=len(S)+1:
        #print(j)
        for k in range(len(dire[j])):
            if S[ind] != tmp[k]:
                flag =0
                j += 1
                break
            else:
                ind = ind + 1
                if k==len(dire[j])-1:
                    i = i + len(dire[j])
                    flag = 1
                    old = len(dire[j])
                    old_j  = j
                    j=0
    else:
        j+=1
        if j==4:
            i=i-old
            j=old_j+1
            flag = 0

    if   j >= 4 and flag == 0 and i != 0:
        i = i - old
        j = old_j+1

    if i >= len(S):
        print('YES')
        break
    elif i <= 0 and j >= 3 and flag == 0:
        print('NO')
        break


### FIXED CODE ###

S = input()
S_r = S[::-1]
dire = ['dream','dreamer','erase','eraser']
dire_r = [0]*4
for i in range(4):
    tmp = dire[i]
    dire_r[i] = tmp[::-1]
ind = 0

excep = 0

while ind  <len(S_r):
    if excep == 1:
        break
    flag2= 0
    for j in range(4):
        if flag2 ==0:
            case = 0
            for k in range(len(dire_r[j])):
                tmp = dire_r[j]

                if ind + k < len(S_r) and case == 0:
                #    print(j)
            #        print('S:'+S_r[ind+k])
            #        print('dire:'+tmp[k])
                    if S_r[ind+k] != tmp[k]:
                        flag = 0
                        case = 1
                        if j == 3:
                            excep = 1

                    elif k== len(dire_r[j])  -1:
                        ind = ind + len(dire_r[j])
                        flag = 1
                        case = 1
                        flag2 = 1


if flag == 1:
    print('YES')
else:
    print('NO')
import math

def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

n, k = map(int, input().split())
x = n - k

div = 10 ** 9 + 7
for i in range(1, k+1):
    print((comb(x+1, i) * comb(k-1, i-1)) % div) 


### FIXED CODE ###

import math

def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

n, k = map(int, input().split())
x = n - k

div = 10 ** 9 + 7
for i in range(1, k+1):
    if (i-1 <= x):
        print((comb(x+1, i) * comb(k-1, i-1)) % div) 
    else:
        print('0')