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

from collections import defaultdict

N = int(input())
S = input()

dd = defaultdict(int)
rList = [0]
gList = [0]
bList = [0]
for i in range(N):
    if S[i] == "R":
        rList.append(rList[-1] + 1)
        gList.append(gList[-1])
        bList.append(bList[-1])
    elif S[i] == "G":
        rList.append(rList[-1])
        gList.append(gList[-1] + 1)
        bList.append(bList[-1])
    else:
        rList.append(rList[-1])
        gList.append(gList[-1])
        bList.append(bList[-1] + 1)

ans = 0
for i in range(N):
    for j in range(i, N):
        if S[i] == S[j]:
            continue
        tl = ["R", "G", "B"]
        tl.remove(S[i])
        tl.remove(S[j])
        target = tl[0]
        if target == "R":
            ans += rList[-1] - rList[j + 1]
        elif target == "G":
            ans += gList[-1] - gList[j + 1]
        else:
            ans += bList[-1] - bList[j + 1]

        diff = abs(i - j)
        if j + diff <= N - 1 and S[j + diff] == target:
            ans -= 1

print(ans)


### FIXED CODE ###

from collections import defaultdict

N = int(input())
S = input()

dd = defaultdict(int)
rList = [0]
gList = [0]
bList = [0]
for i in range(N):
    if S[i] == "R":
        rList.append(rList[-1] + 1)
        gList.append(gList[-1])
        bList.append(bList[-1])
    elif S[i] == "G":
        rList.append(rList[-1])
        gList.append(gList[-1] + 1)
        bList.append(bList[-1])
    else:
        rList.append(rList[-1])
        gList.append(gList[-1])
        bList.append(bList[-1] + 1)

ans = 0
for i in range(N):
    for j in range(i, N):
        if S[i] == S[j]:
            continue
        tl = ["R", "G", "B"]
        tl.remove(S[i])
        tl.remove(S[j])
        target = tl[0]
        if target == "R":
            ans += rList[-1] - rList[j + 1]
        elif target == "G":
            ans += gList[-1] - gList[j + 1]
        else:
            ans += bList[-1] - bList[j + 1]

        diff = abs(i - j)
        if j + diff <= N - 1 and S[j + diff] == target:
            ans -= 1

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

import numpy as np

n = map(int, raw_input().split())

x = map(int, raw_input().split())
n = n[0]
ans = []

x = np.asarray(x)
for i in range(n):
    a = np.ones(n)
    multiple = -1
    for j in range(n):
        a[(i+j)%n] *= multiple
        multiple *= -1
    a[i] = 1
    ans.append(int(np.dot(x, a)))
last = ans.pop()
ans.insert(0, last)
print ' '.join(map(str, ans))


### FIXED CODE ###

import numpy as np

n = map(int, raw_input().split())

x = map(int, raw_input().split())
n = n[0]
ans = []

x = np.asarray(x)
double_x = 2 * x
x0 = 0
multiple = 1
for j in range(n):
    x0 += x[j] * multiple
    multiple *= -1
ans.append(x0)
for i in range(0, n-1):
    ans.append(double_x[i] - ans[i])

print ' '.join(map(str, ans))
### BUGGY CODE ###

def main():
  N = int(input())
  Sp = []
  Sm = []
  total = 0
  for i in range(N):
    l = input()
    b = 0
    h = 0
    bm = 0
    for j in range(len(l)):
      if l[j] == '(':
        h += 1
      else:
        h -= 1
      b = min(b, h)
    if h == 0 and b != 0:
      bm = min(bm, b)
    elif h > 0:
      Sp.append([b, h])
    elif h < 0:
      Sm.append([b-h, -h])
    Sp.append([bm, 0])
    total += h
  if total != 0:
    print('No')
    exit()
  Sp.sort(key=lambda x:x[0], reverse=True)
  p = check(Sp)
  if p < 0:
    print('No')
    exit()
  Sm.sort(key=lambda x:x[0], reverse=True)
  m = check(Sm)
  if m < 0:
    print('No')
    exit()
  print('Yes')

def check(S):
  h = 0
  for i in range(len(S)):
    if h + S[i][0] < 0:
      return -1
    else:
      h += S[i][1]
  return h

if __name__ == '__main__':
  main()

### FIXED CODE ###

import sys
readline = sys.stdin.readline

def main():
  N = int(readline())
  Sp = []
  Sm = []
  total = 0
  bm = 0
  for i in range(N):
    l = readline().strip()
    b = 0
    h = 0
    for j in range(len(l)):
      if l[j] == '(':
        h += 1
      else:
        h -= 1
      b = min(b, h)
    if h == 0 and b != 0:
      bm = min(bm, b)
    elif h > 0:
      Sp.append([b, h])
    elif h < 0:
      Sm.append([b-h, -h])
    total += h
  Sp.append([bm, 0])
  if total != 0:
    print('No')
    exit()
  Sp.sort(key=lambda x:x[0], reverse=True)
  p = check(Sp)
  if p < 0:
    print('No')
    exit()
  Sm.sort(key=lambda x:x[0], reverse=True)
  m = check(Sm)
  if m < 0:
    print('No')
    exit()
  print('Yes')

def check(S):
  h = 0
  for i in range(len(S)):
    if h + S[i][0] < 0:
      return -1
    else:
      h += S[i][1]
  return h

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

import sys
MX = 10**5
def main():
    input = sys.stdin.readline
    N = int(input())
    items = [tuple(map(int, input().split())) for _ in range(N)]
    Q = int(input())
    vL = [tuple(map(int, input().split())) for _ in range(Q)]

    H = min(N + 1, 1 << 9)
    Hb = (H - 1).bit_length()
    dp = [[0] * (MX + 1) for _ in range(H)]
    for i in range(1, H):
        v, w = items[i - 1]
        dpi = dp[i]
        dpip = dp[i >> 1]
        for j in range(MX + 1):
            t = dpip[j]
            if j >= w:
                t = max(t, dpip[j - w] + v)
            dpi[j] = t
    for v, L in vL:
        if v < H:
            print(dp[v][L])
            continue
        ans = 0
        for i in range(1 << (v.bit_length() - Hb)):
            node = v
            value = weight = 0
            while node >= H:
                if i & 1:
                    iv, iw = items[node - 1]
                    value += iv
                    weight += iw
                node >>= 1
                i >>= 1
            if weight > L:
                continue
            ans = max(ans, value + dp[node][L - weight])
        print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
MX = 10**5
def main():
    data = map(int, sys.stdin.buffer.read().split())
    N = next(data)

    H = min(N + 1, 1 << 10)
    dp = [None] * H
    dp[0] = [0] * (MX + 1)
    IV, IW = [], []
    i = 1
    for v, w in zip(data, data):
        if i < H:
            dpi = dp[i >> 1][:]
            dp[i] = dpi
            for j in range(MX, w - 1, -1):
                dpi[j] = max(dpi[j], dpi[j - w] + v)
        else:
            IV.append(v)
            IW.append(w)
        i += 1
        if i > N:
            break

    Q = next(data)
    for v, L in zip(data, data):
        if v < H:
            print(dp[v][L])
            continue

        item_values = []
        item_weights = []
        while v >= H:
            item_values.append(IV[v - H])
            item_weights.append(IW[v - H])
            v >>= 1

        l = len(item_values)
        V = [0] * (1 << l)
        W = [0] * (1 << l)
        ans = dp[v][L]
        for i in range(1, 1 << l):
            msb = i & (-i)
            msbb = msb.bit_length() - 1
            wi = W[i - msb] + item_weights[msbb]
            W[i] = wi
            if wi <= L:
                vi = V[i - msb] + item_values[msbb]
                ans = max(ans, vi + dp[v][L - wi])
                V[i] = vi
        print(ans)

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

import numpy as np
import collections
import math

s = input()[::-1]
length = len(s)
a = []
d = []
for i in range(length):
    a.append(int(s[i]) * pow(10, i) % 2019)
d.append(a[0])
for i in range(length-1):
    d.append((d[i] + a[i+1]) % 2019)
x = np.array([i for i in collections.Counter(d).values()])
x = x[np.where(x > 1)]
print(int(sum([math.factorial(x[i]) for i in range(x.shape[0])]) / 2) + d.count(0))

### FIXED CODE ###

import numpy as np

s = input()[::-1]
length = len(s)
a = np.zeros(length, dtype=int)
d = np.zeros(length, dtype=int)
ans = np.zeros(2019, dtype=int)
x = 10

a[0] = int(s[0])
d[0] = a[0]
ans[d[0]] += 1

for i in range(1, length):
    a[i] = int(s[i]) * x % 2019
    d[i] = (d[i-1] + a[i]) % 2019
    ans[d[i]] += 1
    x = x * 10 % 2019

ans_c = ans[np.nonzero(ans)]

print(int(sum([ans_c[i] * (ans_c[i]-1) for i in range(ans_c.shape[0])]) / 2) + ans[0])
### BUGGY CODE ###

from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n,d,a = inm()
xh = []
for i in range(n):
    xx,hh = inm()
    xh.append((xx,(hh+a-1)//a))
xh.sort()
cnt = 0
for i in range(n):
    h = xh[i][1]
    if h<=0:
        continue
    x = xh[i][0]
    j = i
    while j<n-1 and xh[j+1][0]<=x+2*d:
        j += 1
    for k in range(i,j+1):
        xh[k] = (xh[k][0], xh[k][1]-h)
    cnt += h
print(cnt)


### FIXED CODE ###

from sys import stdout
from collections import deque
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n,d,a = inm()
xh = []
for i in range(n):
    xx,hh = inm()
    xh.append((xx,(hh+a-1)//a))
xh.sort()
cnt = 0
q = deque([])
ad = 0
for i in range(n):
    h = xh[i][1]
    x = xh[i][0]
    while len(q)>0 and q[0][0]<x:
        z = q.popleft()
        ad -= z[1]
    h -= ad
    if h<=0:
        continue
    cnt += h
    ad += h
    q.append((x+2*d,h))
print(cnt)
### BUGGY CODE ###

import sys #追加
sys.setrecursionlimit(500*500)

s = input()
def check_and_cut(string):
    tmp = '123'
    flag = True
    if len(string) <= 4:
        pass
    else:
        if len(string) >4:
            if string[-5:] == 'dream':
                tmp = string[:-5]
                flag = False
            elif string[-5:] == 'erase':
                tmp = string[:-5]
                flag = False
        if len(string) >5 and flag:
            if string[-6:] == 'eraser':
                tmp = string[:-6]
                flag = False
        if len(string) >6 and flag:
            if string[-7:] == 'dreamer':
                tmp = string[:-7]
                flag = False
    #print(string,len(string),string[-6:],tmp,string[-6:] == 'eraser')
    if tmp == '':
        print('YES')
    else:
        if tmp == '123':
            print('NO')
        else:
            check_and_cut(tmp)
check_and_cut(s)
#tmp = 'abcdefg'
#print(tmp[-4:])

### FIXED CODE ###

import sys #追加
sys.setrecursionlimit(500*500)

s = input()
check_flag = True
def check_and_cut(string):
    tmp = '123'
    flag = True
    if len(string) <= 4:
        pass
    else:
        if len(string) >4:
            if string[-5:] == 'dream':
                tmp = string[:-5]
                flag = False
            elif string[-5:] == 'erase':
                tmp = string[:-5]
                flag = False
        if len(string) >5 and flag:
            if string[-6:] == 'eraser':
                tmp = string[:-6]
                flag = False
        if len(string) >6 and flag:
            if string[-7:] == 'dreamer':
                tmp = string[:-7]
                flag = False
    #print(string,len(string),string[-6:],tmp,string[-6:] == 'eraser')
    return tmp
while check_flag:
    t = check_and_cut(s)
    if t == '123':
        print('NO')
        exit()
    if len(t) == 0:
        print('YES')
        exit()
    s = t
### BUGGY CODE ###

n=int(input())
A=list(map(int,input().split()))
mod=10**9+7
sum_=0
for i in range(n-1):
    for j in range(n-i-1):
        sum_ += A[i]*A[i+j+1]
        sum_ %= mod
print(sum_)

### FIXED CODE ###

n=int(input())
A=list(map(int,input().split()))
mod=10**9+7
s=sum(A)
ans=0
for a in A:
    ans += a*(s-a)
print((ans//2)%mod)
### BUGGY CODE ###

A,B,K = map(int,input().split())
for i in range(A,B+1): #AからB
    if i < A+K or B-K < i :
        print(i)


### FIXED CODE ###

A,B,K = map(int,input().split())

if B-A+1 <= K * 2:
    for i in range(A,B+1):
            print(i)

else:
    for i in range(A,A+K): #AからB
        print(i)

    for i in range(B-K+1,B+1):
        print(i)
### BUGGY CODE ###

import numpy as np

N,Q = map(int,input().split())
s = str(input())
S = []
for c in s:
    S.append(c)
l = np.zeros(Q)
r = np.zeros(Q)
for i in range(Q):
    l[i], r[i] = map(int, input().split())

for i in range(Q):
    lst = S[int(l[i]-1):int(r[i])]
    count = 0
    for i in range(len(lst)-1):
        if (lst[i] == "A")and(lst[i+1] == "C"):
            count += 1
    print(count)

### FIXED CODE ###





import numpy as np

N,Q = map(int,input().split())
S = []
for c in str(input()):
    S.append(c)

a = np.zeros(N)
   
for i in range(1,N):
    if (S[i-1] == "A")and(S[i] == "C"):
        a[i] = a[i-1] + 1
    else:
        a[i] = a[i-1]
        
for i in range(Q):
    l, r = map(int, input().split())
    print(int(a[r-1] - a[l-1]))
### BUGGY CODE ###

import sys
from itertools import combinations as combi
input = sys.stdin.readline
H, W, K = map(int, input().split())
S = [list(input())[: -1] for _ in range(H)]
cs = [[0] * (W + 1) for _ in range(H)]
for i in range(H):
  for j in range(W): cs[i][j + 1] = cs[i][j] + int(S[i][j] == "1")
res = H * W
#print(cs)
for t in range(H):
  for c in combi([x for x in range(H - 1)], t):
    l = 0
    tres = 0
    while l < W:
      ok = l
      ng = W + 1
      while ng - ok > 1:
        m = (ok + ng) // 2
        tt = 0
        i = 0
        ttt = 0
        while i < H:
          ttt += cs[i][m] - cs[i][l]
          if i in c:
            tt = max(tt, ttt)
            ttt = 0
          i += 1
        tt = max(tt, ttt)
        if tt <= K: ok = m
        else: ng = m
      l = ok
      tres += int(l < W)

    #print(c, tres)
    res = min(res, tres + len(c))
print(res)

### FIXED CODE ###

import sys
from itertools import combinations as combi
input = sys.stdin.readline
H, W, K = map(int, input().split())
S = [list(input())[: -1] for _ in range(H)]
cs = [[0] * (W + 1) for _ in range(H)]
for i in range(H):
  for j in range(W): cs[i][j + 1] = cs[i][j] + int(S[i][j] == "1")
res = H * W
#print(cs)
for t in range(H):
  for c in combi([x for x in range(H - 1)], t):
    l = 0
    tres = 0
    while l < W:
      ok = l
      ng = W + 1
      while ng - ok > 1:
        m = (ok + ng) // 2
        tt = 0
        i = 0
        ttt = 0
        while i < H:
          ttt += cs[i][m] - cs[i][l]
          if i in c:
            tt = max(tt, ttt)
            ttt = 0
          i += 1
        tt = max(tt, ttt)
        if tt <= K: ok = m
        else: ng = m
      if l == ok:
        tres = H * W
        break
      l = ok
      tres += int(l < W)

    #print(c, tres)
    res = min(res, tres + len(c))
print(res)
### BUGGY CODE ###

import bisect

N = int(input())
L = list(map(int, input().split()))
L.sort()

ans = 0

for i in range(N-1):
    for j in range(i+1, N):
        a = L[i]
        b = L[j]
        l = bisect.bisect_right(L, abs(a-b))
        r = bisect.bisect_left(L, a+b)
        ans += r-l
        if a in L[l:r]:
            ans -= 1
        if b in L[l:r]:
            ans -= 1
        
print(ans//3)

### FIXED CODE ###

import bisect

N = int(input())
L = list(map(int, input().split()))
L.sort()

ans = 0

for i in range(N-1):
    for j in range(i+1, N):
        a = L[i]
        b = L[j]
        l = bisect.bisect_right(L, abs(a-b))
        r = bisect.bisect_left(L, a+b)
        ans += r-l
        if L[l] <= a <= L[r-1]:
            ans -= 1
        if L[l] <= b <= L[r-1]:
            ans -= 1
        
print(ans//3)
### BUGGY CODE ###

#!/usr/bin/env python3

import itertools

mod = 10**9+7

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

count_0 = [0 for _ in range(61)]
count_1 = [0 for _ in range(61)]

for i in range(len(a)):
    num_str = "%061d" % int(bin(a[i])[2:])
    # print(num_str)
    for j in range(len(num_str)):
        if num_str[j] == "0":
            count_0[j] += 1
        else:
            count_1[j] += 1

# print(count_0)
# print(count_1)

ans = 0
count = 1
for i in range(61):
    tmp = count_0[-i-1]*count_1[-i-1]
    ans += tmp*count
    count = (count*2) % mod
print(ans % mod)


# ans = 0
# for x, y in itertools.combinations(a, 2):
#     # print(x ^ y)
#     ans += (x ^ y)

# print(ans % mod)


### FIXED CODE ###

#!/usr/bin/env python3

# mod = 10**9+7

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

# max_digit = 61

# count_0 = [0 for _ in range(max_digit)]
# count_1 = [0 for _ in range(max_digit)]

# for i in range(len(a)):
#     num_str = bin(a[i])[2:]
#     # print(num_str)
#     for j in range(len(num_str)):
#         # print(num_str[-j-1])
#         if num_str[-j-1] == "1":
#             count_1[-j-1] += 1

# # for i in range(max_digit):
# #     count_0[i] = n-count_1[i]

# ans = 0
# count = 1
# for i in range(61):
#     # tmp = count_0[-i-1]*count_1[-i-1]
#     tmp = count_1[-i-1]*(n-count_1[-i-1])
#     ans += tmp*count
#     count = (count*2) % mod
# print(ans % mod)


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

mod = 10**9+7
max_digit = 61

ans = 0
m = 1
for _ in range(max_digit):
    bit = sum(x&m for x in a)
    bit //= m
    non_bit = n - bit
    ans = (ans+bit*non_bit*m)%mod
    m <<= 1
print(ans)
### BUGGY CODE ###

n=int(input())
l=list(map(int,input().split()))
l2=set(l)
c=0
for i in l2:
  if i>l.count(i):
    c+=l.count(i)
  else:
    c+=l.count(i)-i
  
    
    
print(c)

### FIXED CODE ###

from collections import defaultdict
l=defaultdict(int)
n=int(input())
l1=list(map(int,input().split()))
for i in l1:
  l[i]+=1
b=True
lset=set(l1)
answer=0
for i in lset:
  if l[i]!=i:
    if l[i]<i:
      answer+=l[i]
    else:
      answer+=min(l[i]-i,l[i])
print(answer)
### BUGGY CODE ###

#codigng: utf-8
from sys import stdin

N = int(stdin.readline().rstrip())
num = [int(x) for x in stdin.readline().rstrip().split()]
i = 0
Flag = True
while Flag:
    for i, x in enumerate(num):
        if x % 2 == 0:
            num[i] /= 2
        else:
            print(i)
            Flag = False
            break
    else:
        i += 1


### FIXED CODE ###

#codigng: utf-8
from sys import stdin

bin  = list(stdin.readline().rstrip())
one = [x for x in bin if x == '1']

print(len(one))
### BUGGY CODE ###

from collections import deque

def argmax_poss(xs):
    max_value = max(xs)
    out = []
    for i in range(len(xs)):
        if xs[i] == max_value:
            out.append(i)
    return(out)

h,w,m = map(int,input().split())
Ms = []

h_scores = [0 for i in range(h)]
w_scores = [0 for i in range(w)]

record = deque([])

for i in range(m):
  h,w = map(int,input().split())
  record.append((h-1,w-1))
  h_scores[h-1] += 1
  w_scores[w-1] += 1

max_h_poss = argmax_poss(h_scores)
max_w_poss = argmax_poss(w_scores)

out_pos_count = 0 

while record != deque([]):
    item = record.popleft()
    if item[0] in max_h_poss and item[1] in max_w_poss:
        out_pos_count += 1

if len(max_h_poss) * len(max_w_poss) > out_pos_count:
    print(max(h_scores) + max(w_scores))
else:
    print(max(h_scores) + max(w_scores)-1)



### FIXED CODE ###

from collections import deque

h,w,m = map(int,input().split())
Ms = []

h_scores = [0 for i in range(h)]
w_scores = [0 for i in range(w)]

record = set()

for i in range(m):
  h,w = map(int,input().split())
  record.add((h-1,w-1))
  h_scores[h-1] += 1
  w_scores[w-1] += 1

max_h = max(h_scores)
max_w = max(w_scores)
max_h_poss = [i for i,v in enumerate(h_scores) if v == max_h]
max_w_poss = [i for i,v in enumerate(w_scores) if v == max_w]

out_pos_count = 0 

c = False

for i in max_h_poss:
    for j in max_w_poss:
        if (i,j) not in record:
            c = True
            break        

if c:
    print(max(h_scores) + max(w_scores))
else:
    print(max(h_scores) + max(w_scores)-1)
### BUGGY CODE ###

import math
import copy
N = int(input())
A = [0] * N
for i in range(N):
    A[i] = int(input())
#修正ver
X = [0] * N
for i in range(N):
    B = [0] * N
    B = copy.copy(A)
    del B[i]
    max_item = max(B)
    X[i] = max_item
for i in range(N):
    print(X[i])

### FIXED CODE ###

import math
import copy
N = int(input())
A = [0] * N
for i in range(N):
    A[i] = int(input())
#修正ver
max_item = max(A)
count = 0
second_item = 0
for i in range(N):
    if A[i] == max_item:
        count += 1
    elif second_item < A[i]:
        second_item = A[i]
    if count > 1:
        break
X = [0] * N
judge = False
for i in range(N):
    if count > 1:
        judge = True
        break
    if A[i] == max_item:
        X[i] = second_item
    else:
        X[i] = max_item

if judge:
    for i in range(N):
        X[i] = max_item
for i in range(N):
    print(X[i])
### BUGGY CODE ###

s = input()
q = int(input())
for i in range(q):
    q_i = input()
    if q_i == '1':
        s = ''.join(list(s)[::-1])
    else:
        a, f, c = q_i.split()
        if f == '1':
            s = c+s
        else:
            s = s+c
print(s)
    

### FIXED CODE ###

from collections import deque

s = input()
q = int(input())
queries = [input().split() for _ in range(q)]

judge = True
S = deque()
for string in s:
    S.append(string)

for query in queries:
    if query[0] == '1':
        judge = not judge
    else:
        if judge:
            if query[1] == '1':
                S.appendleft(query[2])
            else:
                S.append(query[2])
        else:
            if query[1] == '1':
                S.append(query[2])
            else:
                S.appendleft(query[2])
ans = ''.join(S)
if not judge:
    print(ans[::-1])
else:
    print(ans)
### BUGGY CODE ###

from queue import PriorityQueue as PQ

INF = float('inf')
yen = 10**15

def pcc(src, adj):
	global n
	pq = PQ()
	dist = [INF]*(n+1)
	dist[src] = 0
	pq.put([0,src])
	while not pq.empty():
		d,u = pq.get()
		for w, v in adj[u]:
			if dist[v] > dist[u] + w:
				dist[v] = dist[u] + w
				pq.put([dist[v], v])
	return dist

n,m,s,t = (int(i) for i in input().split())
adjs = []
adjt = []
for i in range(n+1):
	adjs += [[]]
	adjt += [[]]
for i in range(m):
	u,v,a,b = (int(i) for i in input().split())
	adjs[u].append([a,v])
	adjs[v].append([a,u])
	adjt[u].append([b,v])
	adjt[v].append([b,u])

dist_s = pcc(s,adjs)
dist_t = pcc(t,adjt)



ans = [0]*(n+1)
ans[n] = dist_s[n] + dist_t[n]
for i in range(n-1,0,-1):
	ans[i] = min(ans[i+1], dist_s[i] + dist_t[i])
for i in range(1,n+1):
	print(yen-ans[i])


### FIXED CODE ###

import heapq
def dijkstra(s, neighbor):
	dist = [float('inf')] * N
	dist[s] = 0
	que = [(0, s)]
	heapq.heapify(que)
	while que:
		d, v = heapq.heappop(que)
		if d > dist[v]:
			continue
		for u, l in neighbor[v]:
			tmp_d = d + l
			if tmp_d < dist[u]:
				dist[u] = tmp_d
				heapq.heappush(que, (tmp_d, u))
	return dist
 
N, M, s, t = map(int, input().split())
yen = [[] for _ in range(N)]
snuuk = [[] for _ in range(N)]
for _ in range(M):
	u, v, a, b = map(int, input().split())
	yen[u-1].append((v-1, a))
	yen[v-1].append((u-1, a))
	snuuk[u-1].append((v-1, b))
	snuuk[v-1].append((u-1, b))
 
dist_s = dijkstra(s-1, yen)
dist_t = dijkstra(t-1, snuuk)
ans = [-1] * N
tmp = float('inf')
for i in range(N-1, -1, -1):
	if dist_s[i] + dist_t[i] < tmp:
		tmp = dist_s[i] + dist_t[i]
	ans[i] = 10 ** 15 - tmp
print(*ans, sep='\n')
### BUGGY CODE ###

N = int(input())
A = []
for _ in range(N):
    a = int(input())
    A.append(a)

B = []
for i in range(N):
    B = A[:]
    B.pop(i)
    B.sort()
    print(B.pop())


### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())
A = [int(input()) for _ in range(N)]
amax = max(A)
amaxcnt = A.count(amax)

for i in range(N):
    ai = A[i]
    if ai == amax and amaxcnt == 1:
        A.pop(i)
        print(max(A))
        A.insert(i, 0)
    else:
        print(amax)