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

N = int(input())
A = [int(a) for a in input().split(' ')]

counter = 0

for i in range(N):
    d = 0
    flag = True
    check_list = [0 for j in range(20)]

    while flag:
        counter = counter + 1
        A_test = A[i+d]

        for k in range(20):

            if flag and A_test % (2 ** (k+1))  != 0 and check_list[k] > 0:
                counter = counter - 1
                d = 0
                flag = False

            elif A_test % (2 ** (k+1))  != 0:
                check_list[k] = check_list[k] + 1
                A_test = A_test - (2 ** k)


        if i + d + 1 >= N:
            flag = False
        else:
            d = d + 1

print(counter)


### FIXED CODE ###

N = int(input())
A = [int(a) for a in input().split(' ')]

counter = 0

l = 0
r = 0
flag = True
xor = 0
sum = 0

while r < N and l < N:
    if flag:
        xor ^= A[r]
        sum += A[r]
        if xor == sum:
            counter += (r - l + 1)
        else:
            flag = False
    else:
        xor ^= A[l-1]
        sum -= A[l-1]
        if xor == sum:
            counter += r - l + 1
            flag = True

    if flag:
        r += 1
    else:
        l += 1

print(counter)
### BUGGY CODE ###

[N,L] = [int(x) for x in input().split()]
A = {}
ANS = {}
count = 0
for i,x in enumerate(input().split()):
    i = int(i)
    x = int(x)
    if x in A : A[x] += [i]
    else : A[x] = [i]
for i in sorted(A) :
    for j in A[i] :
        for k in range(L) :
            if j + k not in ANS :
                ANS[j+k] = i
for i in range(L-1,N-1) : print(ANS[i], end=" ")
print(ANS[N-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

import sys
import bisect
input = sys.stdin.readline
A, B, Q = map(int, input().split())
s = [int(input()) for _ in range(A)]
t = [int(input()) for _ in range(B)]
s = sorted(s)
t = sorted(t)

for _ in range(Q):
    x = int(input())
    idx1 = bisect.bisect_right(s, x)
    idx2 = bisect.bisect_right(t, x)
    ans = float('inf')
    if idx1 > 0:
        left_s = s[idx1-1]
    else:
        left_s = float('inf')
    if idx2 > 0:
        left_t = t[idx2-1]
    else:
        left_t = float('inf')
    if idx1 < A:
        right_s = s[idx1]
    else:
        right_s = float('inf')
    if idx2 < B:
        right_t = t[idx2]
    else:
        right_t = float('inf')

    #print(left_s, right_s)
    #print(left_t, right_t)
    if left_s <= x <= right_t:
        tmp = right_t-left_s + min(x-left_s, right_t-x)
        ans = min(ans, tmp)
    if left_t <= x <= right_s:
        tmp = right_s-left_t + min(x-left_t, right_s-x)
        ans = min(ans, tmp)
    ans = min(ans, max(abs(x-left_s), abs(x-left_t)))
    ans = min(ans, max(abs(right_s-x), abs(right_t-x)))
    print(ans)


### FIXED CODE ###

import sys
import bisect
input = sys.stdin.readline
A, B, Q = map(int, input().split())
s = [int(input()) for _ in range(A)]
t = [int(input()) for _ in range(B)]
s = sorted(s)
t = sorted(t)

for _ in range(Q):
    x = int(input())
    idx1 = bisect.bisect_right(s, x)
    idx2 = bisect.bisect_right(t, x)
    ans = float('inf')
    if idx1 > 0:
        left_s = s[idx1-1]
    else:
        left_s = float('inf')
    if idx2 > 0:
        left_t = t[idx2-1]
    else:
        left_t = float('inf')
    if idx1 < A:
        right_s = s[idx1]
    else:
        right_s = float('inf')
    if idx2 < B:
        right_t = t[idx2]
    else:
        right_t = float('inf')

    ls = x-left_s
    lt = x-left_t
    rs = right_s-x
    rt = right_t-x 
    if left_s <= x <= right_t:
        tmp = right_t-left_s + min(ls, rt)
        ans = min(ans, tmp)
    if left_t <= x <= right_s:
        tmp = right_s-left_t + min(lt, rs)
        ans = min(ans, tmp)
    ans = min(ans, max(abs(ls), abs(lt)))
    ans = min(ans, max(abs(rs), abs(rt)))
    print(ans)
### BUGGY CODE ###

X = list(input())

q_num = X.count("?")
a_num = 0
c_num = X.count("C")
left_q_num = 0
right_q_num = q_num
ans = 0
len_x = len(X)
if X[0] == "?":
    right_q_num -= 1
elif X[0] == "C":
    c_num -= 1
for i, x in enumerate(X):
    if x == "B" or x == "?":
        ans += (a_num * c_num)  * (3 ** (left_q_num + right_q_num))
        if left_q_num + right_q_num >= 2:
            ans += (right_q_num * left_q_num  + 3*(left_q_num * c_num) + 3*(right_q_num * a_num)) * (3 ** (left_q_num + right_q_num - 2))
        elif left_q_num + right_q_num == 1:
            ans += ((left_q_num * c_num) + (right_q_num * a_num)) * (3 ** (left_q_num + right_q_num - 1))
        ans = ans % (10 ** 9 + 7)
    if  i == len_x - 1:
        break
    if x == "A":
        a_num += 1
    elif x == "?":
        left_q_num += 1
    if X[i + 1] == "C":
        c_num -= 1
    elif X[i + 1] == "?":
        right_q_num -= 1

print(ans % (10 ** 9 + 7))



### FIXED CODE ###

X = list(input())

q_num = X.count("?")
a_num = 0
c_num = X.count("C")
left_q_num = 0
right_q_num = q_num
ans = 0
len_x = len(X)
q_dict = []
b_ans = 0
q_ans = 0
q_dict = {}
q_dict[q_num - 1] = (3 ** (q_num - 1)) % (10 ** 9 + 7)
q_dict[q_num - 2] = (3 ** (q_num - 2)) % (10 ** 9 + 7)
q_dict[q_num - 3] = (3 ** (q_num - 3)) % (10 ** 9 + 7)
q_dict[q_num] = (3 ** (q_num)) % (10 ** 9 + 7)

if X[0] == "?":
    right_q_num -= 1
elif X[0] == "C":
    c_num -= 1
for i, x in enumerate(X):
    if x == "B" or x == "?":
        ans += (a_num * c_num)  * (q_dict[(left_q_num + right_q_num)])
        if left_q_num + right_q_num >= 2:
            ans += (right_q_num * left_q_num  + 3*(left_q_num * c_num) + 3*(right_q_num * a_num)) * (q_dict[(left_q_num + right_q_num - 2)])
        elif left_q_num + right_q_num == 1:
            ans += ((left_q_num * c_num) + (right_q_num * a_num)) * (q_dict[(left_q_num + right_q_num - 1)])
        ans = ans % (10 ** 9 + 7)
    if  i == len_x - 1:
        break
    if x == "A":
        a_num += 1
    elif x == "?":
        left_q_num += 1
    if X[i + 1] == "C":
        c_num -= 1
    elif X[i + 1] == "?":
        right_q_num -= 1

print(ans % (10 ** 9 + 7))
### BUGGY CODE ###

N = int(input())						# 5
A = list( map(int, input().split()) )	# 1 2 3 4 5 ...
B = list( map(int, input().split()) )	# 1 2 3 4 5 ...


def F(N,A,B):
	dp=[0]*(N+1)
	for n in range(N+1):
		v=n
		for a,b in zip(A,B):
			if n>=a:
				v = max(v, dp[n-a]+b)
		dp[n]=v

		#dp[n] = max(n, max(dp[n-a]+b for a,b in zip(A,B) if n>=a))
	
	return dp[N]

print( F(F(N,A,B),B,A) )


### FIXED CODE ###

N = int(input())						# 5
A = list( map(int, input().split()) )	# 1 2 3 4 5 ...
B = list( map(int, input().split()) )	# 1 2 3 4 5 ...


def F(N,A,B):
	dp=[0]*(N+1)
	for n in range(N+1):
		v=n
		for i in range(3):
			if n>=A[i]:
				x = dp[n-A[i]]+B[i]
				if x>v:
					v = x
		dp[n]=v

		#for a,b in zip(A,B):
		#	if n>=a:
		#		v = max(v, dp[n-a]+b)
		#dp[n]=v

		#dp[n] = max(n, max(dp[n-a]+b for a,b in zip(A,B) if n>=a))
	
	return dp[N]

ans = F(F(N,A,B),B,A)
print( ans )
### BUGGY CODE ###

class Problem:
  def __init__(self, score, number, bonus):
    self.score = score
    self.number = number
    self.bonus = bonus
    
  def score_at(self, number):
    if number >= self.number:
      return self.number * self.score + self.bonus
    return number * self.score


D, G = (int(x) for x in input().split())

problems = []

for i in range(1, D + 1):
  n, b = (int(x) for x in input().split())
  problems.append(Problem(i * 100, n, b))

memo = [[0] * 1001 for _ in range(D)]

def solve():
  for number in range(0, 1001):  # 解いた問題数
    for i in range(D):
      # 一行目の初期化
      if i == 0:
        memo[i][number] = problems[i].score_at(number)
      else:
        memo[i][number] = max(
          memo[i - 1][number - n] +problems[i].score_at(n)
          for n in range(0, number + 1)
        )
    if memo[D - 1][number] >= G:
      return number

print(solve())  

### FIXED CODE ###

import sys

INF = sys.maxsize
D, G = map(int, input().split())

class P:
  def __init__(self, index, number, bonus):
    self.index = index
    self.number = number
    self.bonus = bonus
    
  @property
  def score(self):
    return (self.index + 1) * 100
   
  @property
  def complete_score(self):
    return self.score * self.number + self.bonus
  
  # score 獲得するのに必要な解答数
  def cost_of(self, score):
    if score > self.complete_score:
      return INF
    if score == 0:
      return 0
    if score < self.score:
      return 1
    return min(score // self.score, self.number)
  
problems = []
for i in range(D):
  p, c = map(int, input().split())
  problems.append(P(i, p, c))
  
min_number_of_solved = INF

for m in range(1 << D):
  total = 0
  number_of_solved = 0
  uncompleted = set()
  
  for i, p in enumerate(problems):
    if 1 << i & m:  # 完答
      total += p.complete_score
      number_of_solved += p.number
    else:
      uncompleted.add(p)

  # 他の問題を解かなくても条件を満たしている
  if total >= G:
    min_number_of_solved = min(
      min_number_of_solved, 
      number_of_solved
    )
  # 残りの必要点数を最小コストで獲得できる問題を中途半端に解く
  else:
    # 不足する点を最小コストで獲得できる問題を探す
    m = min(uncompleted, key=lambda x: x.cost_of(G - total))
        
    min_number_of_solved = min(
      min_number_of_solved, 
      number_of_solved + m.cost_of(G - total)
    )
                   
print(min_number_of_solved)
### BUGGY CODE ###

x=input()
while 'ST' in x:
    x=x.replace('ST','')
print(len(x))


### FIXED CODE ###

x=input()
l=len(x)
c=0
ans=0
for i in range(l):
    if x[i]=='S':
        c+=1
    else:
        if c>0:
            ans+=1
        c-=1
    if c<0:
        c+=1
print(l-ans*2)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**8)
from functools import lru_cache

K = input()
N = len(K)
D = int(input())
MOD = 10 ** 9 + 7

@lru_cache(maxsize=10000000)
def f(digit, current_sum, flag):
    if digit == -1:
        if current_sum % D == 0:
            return 1
        else:
            return 0

    ret = 0
    for i in range(10):
        if flag or i < int(K[N-1-digit]):
            ret += f(digit-1, (current_sum+i)%D, 1)
        elif i == int(K[N-1-digit]):
            ret += f(digit-1, (current_sum+i)%D, 0)
    
    return ret % MOD

#substract 0 case
ans = (f(N-1, 0, 0) - 1) % MOD
print(ans)


### FIXED CODE ###

K = input()
N = len(K)
D = int(input())
MOD = 10 ** 9 + 7

dp = [[[0 for k in range(2)] for j in range(D)] for i in range(N+1)]

dp[0][0][0] = 1
for i, n in enumerate(K):
    n = int(n)
    for j in range(D):
        for k in range(2):
            for d in range(10 if k else n+1):
                dp[i+1][(j+d) % D][k or d < n] += dp[i][j][k]
                dp[i+1][(j+d) % D][k or d < n] %= MOD

print((dp[N][0][0] + dp[N][0][1] - 1) % MOD)
### BUGGY CODE ###

import functools
import operator


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

prod = functools.partial(functools.reduce, operator.mul)
if 10 ** 18 < prod(A):
    print(-1)
else:
    print(prod(A))

### FIXED CODE ###

def ans(a):
    ans = 1
    if 0 in a:
        return 0
    for i in A:
        ans *= i
        if 10 ** 18 < ans:
            ans = -1
            return ans
    return ans


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

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

n = input()
l = list(raw_input())
ans = n

for i in range(0, n):
  tmp = l[:i].count("W") + l[i+1:].count("E")
  if tmp < ans:
    ans = tmp

print ans

### FIXED CODE ###

n = input()
l = list(raw_input())
left = 0
right = l.count("E")
count = []

for i in range(0, n):
	if l[i] == "E":
		right -= 1

	count += [left + right]

	if l[i] == "W":
		left += 1

print min(count)
### BUGGY CODE ###

def osilate(seq):
    flag = 1
    acc = 0
    ans = 0
    while len(seq) > 0:

        a = seq[0]
        acc += a

        if flag > 0:
            if acc <= 0:
                ans += 1-acc
                acc = 1
        if flag < 0:
            if acc >= 0:
                ans += 1+acc
                acc = -1
        #print(seq, acc, ans)
        seq.pop(0)
        flag = flag * (-1)
    return ans

n = int(input())
seq = [int(i) for i in input().split()]
acc = []
tmp = 0

seq_rev = [-i for i in seq]
print(min(osilate(seq),osilate(seq_rev)))



### FIXED CODE ###

def osilate(seq):
    flag = 1
    acc = 0
    ans = 0
    #while loop O(n)
    for i in range(len(seq)):
        a = seq[i]
        acc += a
        flag = i%2

        if flag == 0:
            if acc <= 0:
                ans += 1-acc
                acc = 1
        if flag == 1:
            if acc >= 0:
                ans += 1+acc
                acc = -1
        #print(seq, acc, acc)
        flag = flag * (-1)
    return ans

n = int(input()) #(1)
seq = [int(i) for i in input().split()] #O(N)

seq_rev = [-i for i in seq]  # O(N)
print(min(osilate(seq),osilate(seq_rev))) #O(2N)
### BUGGY CODE ###

import itertools
N = int(input())
S = list(input())
se = set(itertools.combinations(S,3))
print(len(se))


### FIXED CODE ###

from collections import defaultdict
n = int(input())
S = input()

d1 = defaultdict(int)
d2 = defaultdict(int)
d3 = defaultdict(int)

for s in S:
    for x in d2:
        d3[x+s]+=1
    for y in d1:
        d2[y+s]+=1
    d1[s]+=1

print(len(d3))
### BUGGY CODE ###

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

# 全ての組み合わせ数
allcnt = S.count("R") * S.count("G") * S.count("B")

# 除外するものチェック
rem = 0
for i in range(N-2):
  for j in range(i+1,N-1):
    k = j + (j - i)
    if k >= N:
      break
    if len(set([S[i],S[j],S[k]])) == 3:
      rem += 1
print(allcnt - rem)


### FIXED CODE ###

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

# 全ての組み合わせ数
allcnt = S.count("R") * S.count("G") * S.count("B")

# 除外するものチェック
rem = 0
for i in range(N-2):
  for j in range(i+1,N-1):
    k = j + (j - i)
    if k >= N:
      break
    if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
      rem += 1
print(allcnt - rem)
### BUGGY CODE ###

def minus_point(num,point,N):
    for i in range(N):
        if i != num-1:
            point[i] = point[i] - 1
        else:
            continue

    
        
N,K,Q = map(int, input().split(" "))
A = []
point = []
for i in range(Q):
    A.append(int(input()))

for i in range(N):
    point.append(K)



for i in range(Q):
    minus_point(A[i], point, N)

for i in range(N):
    if point[i] > 0:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

n,k,q = map(int,input().split(" "))
point = [k-q] * n
for i in range(0,q):
    point[int(input())-1] += 1
for j in range(0,n):
    if point[j] > 0:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

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

def solve(a,b,c,k):
  s = 0
  while k > 0:
    if a > 0:
      a -= 1
      s += 1
      k -= 1
    elif b > 0:
      b -= 1
      k -= 1
    else:
      c -= 1
      s -= 1
      k -= 1

  return s
    
print(solve(A,B,C,K))

### FIXED CODE ###

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

def solve(a,b,c,k):
  if a >= k:
    return k
  elif a + b >= k:
    return a
  else:
    return a-(k-a-b)
    
print(solve(A,B,C,K))
### BUGGY CODE ###

from collections import defaultdict
from heapq import heappop, heappush
 
class Graph:
 
    def __init__(self):
        self.graph = defaultdict(list)
        self.vertices = set()
        self.edges = []
 
    def add_edge(self, a, b, weight=1):
        self.graph[a].append((b, weight))
        self.vertices |= {a, b}
        self.edges.append((a, b, weight))

        self.graph[b].append((a, weight))
        self.edges.append((b, a, weight))
 
    def get_vertices(self):
        return sorted(list(self.vertices))
 
    def num_of_vertices(self):
        return len(self.vertices)
 
    def get_edges(self):
        return self.edges
 
    def num_of_edges(self):
        return len(self.edges)
 
class Dijkstra:
 
    def __init__(self, graph, start):
        self.g = graph.graph
 
        self.dist = defaultdict(lambda: float("inf"))
        self.dist[start] = 0
 
        self.prev = defaultdict(lambda: None)
 
        self.Q = []
        heappush(self.Q, (0, start))
 
        while self.Q:
            dist_u, u = heappop(self.Q)
 
            if self.dist[u] < dist_u:
                continue
 
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))
 
 
    def shortest_distance(self, goal):
 
        return self.dist[goal]
 
    def shortest_path(self, goal):
 
        path = []
        vertice = goal
        while vertice is not None:
            path.append(vertice)
            vertice = self.prev[vertice]
 
        return path[::-1]

G = Graph()
N = int(input())
for i in range(N-1):
    a, b, c = map(int, input().split())
    G.add_edge(a, b, c)

Q, K = map(int, input().split())
for _ in range(Q):
    x, y = map(int, input().split())
    D1 = Dijkstra(G, x)
    D2 = Dijkstra(G, K)
    print(D1.shortest_distance(K)+D2.shortest_distance(y))
    


### FIXED CODE ###

from collections import deque
N = int(input())
D = [[] for _ in range(N)]
for _ in range(N-1):
    a, b, c = map(int, input().split())
    a, b = a-1, b-1
    D[a].append((b, c))
    D[b].append((a, c))

cnt, K = map(int, input().split())
K -= 1
Q = deque([(K, 0)])
Dist = [0]*N
check = [0]*N
while Q:
    n, d = Q.popleft()
    check[n] = 1
    Dist[n] = d
    for v, e in D[n]:
        if check[v]:
            continue
        else:
            Q.append((v, d+e))

for _ in range(cnt):
    x, y = map(int, input().split())
    x, y = x-1, y-1
    print(Dist[x]+Dist[y])
### BUGGY CODE ###

def resolve():
    (N, Q) = list(map(int, input().split(" ")))
    S = input()
    LRs = [list(map(int, input().split(" "))) for i in range(Q)]
    mem = [S[i:i+2] == "AC" for i in range(N-1)]

    for (l, r) in LRs:
        print(sum(mem[l-1:r-1]))

if '__main__' == __name__:
    resolve()

### FIXED CODE ###

def resolve():
    (N, Q) = list(map(int, input().split(" ")))
    S = input()
    LRs = [list(map(int, input().split(" "))) for i in range(Q)]
    mem = [0] * N
    for i in range(N-1):
        if S[i] == "A" and S[i+1] == "C":
            mem[i+1] = mem[i] + 1
        else:
            mem[i+1] = mem[i]

    for (l, r) in LRs:
        print(mem[r-1]-mem[l-1])

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

s = list(input())
t = list(input())

dp = [ [ "" for i in range(3010)] for j in range(3010) ]

for i in range(len(s)):
    for j in range(len(t)):
        if s[i] == t[j]:
            if len(dp[i+1][j+1]) <= len(dp[i][j])+1:
                dp[i+1][j+1] = dp[i][j] + s[i]
        else:
            if len(dp[i+1][j+1]) <= len(dp[i+1][j]):
                dp[i+1][j+1] = dp[i+1][j]
            if len(dp[i+1][j+1]) <= len(dp[i][j+1]):
                dp[i+1][j+1] = dp[i][j+1]

print(dp[len(s)][len(t)])

### FIXED CODE ###

s = list(input())
t = list(input())

dp = [ [ 0 for i in range(3010)] for j in range(3010) ]

for i in range(len(s)):
    for j in range(len(t)):
        if s[i] == t[j]:
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + 1)
        else:
            dp[i+1][j+1] = max(dp[i+1][j+1],dp[i+1][j])
            dp[i+1][j+1] = max(dp[i+1][j+1],dp[i][j+1])

i = len(s)-1
j = len(t)-1
ans = ""

while (i>=0 and j>=0):
    if dp[i+1][j+1] == dp[i+1][j]:
        j -= 1
    elif dp[i+1][j+1] == dp[i][j+1]:
        i -= 1
    else:
        ans = s[i] + ans
        i -= 1
        j -= 1

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

N = int(input())
A = list(map(str, input().split())) 
for i in range(N-1): 
    print(A.count("{}".format(i+1)))
print(0) 

### FIXED CODE ###

import collections

N = int(input())
A = list(map(str, input().split())) 
c = collections.Counter(A)  
for i in range(N):
    print(c["{}".format(i+1)])
### BUGGY CODE ###

# 各要素に身長同士の和を保持する行列を利用する方法
import numpy as np

n = int(input())
a = np.array(list(map(int, input().split())))
s = np.array([])
for i in a:
    s = np.append(s, i+a)
s = s.reshape(len(a), -1)
for i in range(len(a)):
    s[i, i] = -1
b = np.arange(1, n+1)
t = np.array([])
for i in b:
    t = np.append(t, abs(b-i))
t = t.reshape(len(b), -1)
print(int(np.count_nonzero(s == t)/2))

### FIXED CODE ###

from collections import defaultdict
n = int(input())
a = list(map(int, input().split()))
ci = defaultdict(int)
cj = defaultdict(int)
for i in range(n):
    ci[a[i]+i] += 1
    cj[i-a[i]] += 1
cnt = 0
for k in ci.keys():
    cnt += ci[k] * cj[k]
print(cnt)
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline
from scipy.sparse.csgraph import csgraph_from_dense,dijkstra

def main():
    N,M,s,t = map(int,input().split())
    INF = 10**15
    
    yedge = [[INF for _ in range(N)] for _ in range(N)]
    sedge = [[INF for _ in range(N)] for _ in range(N)]
    for _ in range(M):
        u,v,a,b = map(int,input().split())
        yedge[u-1][v-1] = yedge[v-1][u-1] = a
        sedge[u-1][v-1] = sedge[v-1][u-1] = b
    
    Gy,Gs = dijkstra(csgraph_from_dense(yedge,null_value=INF),indices=s-1),dijkstra(csgraph_from_dense(sedge,null_value=INF),indices=t-1)
    
    al = []
    ans = 0
    for i,j in zip(Gy[::-1],Gs[::-1]):
        ans = max(ans,int(INF-i-j))
        al.append(ans)

    print(*al[::-1],sep="\n")
if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
import heapq

def main():
    N,M,s,t = map(int,input().split())
    INF = 10**15
    
    yedge = [[] for _ in range(N)]
    sedge = [[] for _ in range(N)]
    for _ in range(M):
        u,v,a,b = map(int,input().split())
        yedge[u-1].append((a,v-1))
        yedge[v-1].append((a,u-1))
        sedge[u-1].append((b,v-1))
        sedge[v-1].append((b,u-1))
        
    def dij(x,z):
        q = [(0,x)]
        heapq.heapify(q)
        go = [INF for _ in range(N)]
        go[x] = 0
        while q:
            d,now = heapq.heappop(q)
            if go[now] > d:
                continue
            for d,fol in z[now]:
                if go[fol] > go[now]+d:
                    go[fol] = go[now]+d
                    heapq.heappush(q,(go[fol],fol))
        return go
        
    y,s = dij(s-1,yedge),dij(t-1,sedge)
    ans = []
    u = 0
    for i,j in zip(y[::-1],s[::-1]):
        u = max(u,INF-i-j) 
        ans.append(u)
        
    print(*ans[::-1],sep="\n")

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

k, s = map(int, input().split())
ans = 0
for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if x+y+z == s:
                ans += 1
print(ans)

### FIXED CODE ###

k, s = map(int, input().split())
ans = 0
for x in range(k+1):
    if x > s:
        break
    else:
        for y in range(k+1):
            if x+y > s:
                break
            elif s - x - y <= k:
                ans += 1
print(ans)
### BUGGY CODE ###

n = int(input())

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

ans = 0
dx = 10 ** 9 + 7
for i in range(n):
    for j in range(i+1, n):
        ans += a[i] * a[j]
        ans %= dx

print(ans)


### FIXED CODE ###

n = int(input())

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

S = sum(a)

S2 = sum(map(lambda x: x * x, a ))

ans = (S * S - S2) // 2 % 1000000007
print(ans)
### BUGGY CODE ###

import numpy as np

N, K = [int(i) for i in input().split()]
P = [int(p) for p in input().split()]

max_P = []
max = 0
for i in range(N-K+1):
    sum_dice = np.sum(P[i:i+K])
    if sum_dice > max:
        max = sum_dice
        max_P = P[i:i+K]

ans = 0
for p in max_P:
    ans += np.sum(np.arange(1,p+1))/p

print(ans)

### FIXED CODE ###

import numpy as np

N, K = [int(i) for i in input().split()]
P = [int(p) for p in input().split()]

max = 0
sum = 0
for i in range(N):
    sum += P[i]
    if i >= K:
        sum -= P[i-K]
    if max < sum:
        max = sum
print((max+K)/2)