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

import math
n = int(input())

def yakusu(n):
    a = []
    for i in range(1, int(math.sqrt(2*n))+2):
        if(2*n % i == 0):
            a.append(i)
    for i in range(len(a)):
        a.append(2*n // a[i])
    return sorted(list(set(a)))

def exgcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = exgcd(b % a, a)
        return g, x - (b // a) * y, y
    
def CRT(b1, m1, b2, m2):
    # 中国剰余定理
    # x ≡ b1 (mod m1) ∧ x ≡ b2 (mod m2) <=> x ≡ r (mod m)
    # となる(r. m)を返す
    # 解無しのとき(0, -1)
    d, p, q = exgcd(m1, m2)
    if (b2 - b1) % d != 0:
        return 0, -1
    m = m1 * (m2 // d)  # m = lcm(m1, m2)
    tmp = (b2-b1) // d * p % (m2 // d)
    r = (b1 + m1 * tmp) % m
    return r, m
x = yakusu(n)
a = 1e16
for i in range(len(x)):
    r, m = CRT(-1, 2*n//x[i], 0, x[i])
    if(r > 0):
        a = min(a, r)
print(a)

### FIXED CODE ###

import math
n = int(input())

def yakusu(n):
    a = []
    for i in range(1, int(math.sqrt(2*n))+2):
        if(2*n % i == 0):
            a.append(i)
    for i in range(len(a)):
        a.append(2*n // a[i])
    return sorted(list(set(a)))

def exgcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = exgcd(b % a, a)
        return g, x - (b // a) * y, y
    
def CRT(b1, m1, b2, m2):
    # 中国剰余定理
    # x ≡ b1 (mod m1) ∧ x ≡ b2 (mod m2) <=> x ≡ r (mod m)
    # となる(r. m)を返す
    # 解無しのとき(0, -1)
    d, p, q = exgcd(m1, m2)
    if (b2 - b1) % d != 0:
        return 0, -1
    m = m1 * (m2 // d)  # m = lcm(m1, m2)
    tmp = (b2-b1) // d * p % (m2 // d)
    r = (b1 + m1 * tmp) % m
    return r, m
x = yakusu(n)
a = 1e16
for i in range(len(x)):
    r, m = CRT(-1, 2*n//x[i], 0, x[i])
    if(r > 0):
        a = min(a, r)
print(a)
### BUGGY CODE ###

import queue

if __name__ == "__main__":
    X = int(input())
    q = queue.Queue()
    qq = queue.Queue()
    q.put((0, 0))
    while True:
        x, t = q.get()
        if x == X :
            print(t)
            break
        t += 1
        q.put((x, t))
        q.put((x+t, t))
        q.put((x-t, t))

### FIXED CODE ###

if __name__ == "__main__":
    X = int(input())
    s = 0
    i = 0
    while True:
        s += i
        if s >= X:
            print(i)
            break
        i += 1
### BUGGY CODE ###

import itertools

n, m, r = [ int(v) for v in input().split() ]
town_list = [ int(v)-1 for v in input().split() ]

road_matrix = [ [ 10**9 for j in range(n) ] for i in range(n) ]


for i in range(m):
	s, e, d = [ int(v) - 1 for v in input().split() ]
	road_matrix[s][e] = d + 1
	road_matrix[e][s] = d + 1


min_dist_matrix = []
for h in range(n):
	min_dist = road_matrix[h]
	searched_point = []
	sarching_point = []
	j = h
	while len(searched_point) < n:
		searched_point.append(j)
		for i in range(n):
			if road_matrix[j][i] != 10**9 and i != h:
				sarching_point.append((road_matrix[j][i],i))
				min_dist[i] = min(min_dist[i],min_dist[j] + road_matrix[j][i])
		sarching_point.sort()

		for k in range(len(sarching_point)):
			if sarching_point[k][1] not in searched_point:
				j = sarching_point[k][1]
				sarching_point = sarching_point[k+1:]
				break
	min_dist_matrix.append(min_dist)


mindist = 10**9
for i in itertools.permutations(town_list,r):
	dist = 0
	for j in range(r-1):
		dist += min_dist_matrix[i[j]][i[j+1]]

	mindist = min(mindist,dist)
print(mindist)

### FIXED CODE ###

import itertools
import sys
input = sys.stdin.readline

n, m, r = [ int(v) for v in input().split() ]
town_list = [ int(v)-1 for v in input().split() ]

road_matrix = [ [ 10**9 for j in range(n) ] for i in range(n) ]


for i in range(m):
	s, e, d = [ int(v) - 1 for v in input().split() ]
	road_matrix[s][e] = d + 1
	road_matrix[e][s] = d + 1


for k in range(n):
	 for i in range(n):
		 for j in range(n):
			 road_matrix[i][j]  = min(road_matrix[i][k] + road_matrix[k][j], road_matrix[i][j])


mindist = 10**9
for i in itertools.permutations(town_list,r):
	dist = 0
	for j in range(r-1):
		dist += road_matrix[i[j]][i[j+1]]

	mindist = min(mindist,dist)
print(mindist)
### BUGGY CODE ###

import numpy as np
inp1 = input()
inp2 = input().split()

a = int(inp1)
b = np.array(inp2).astype(int)
ansno = a

for ii,i in enumerate(b):
  bslice = b[:ii+1]
  minb = np.min(bslice)
  if minb == i:
    pass
  else:
    ansno -=1

print(ansno)

### FIXED CODE ###

n = int(input())
m = input().split()
ppp = list(map(int, m))
max = 2*10**5+1
ans = 0
for p in ppp:
    if p < max:
        ans += 1
        max = p
print(ans)
### BUGGY CODE ###

S = str(input())
l = len(S)
mod = [0] * 2019
dp = 0
for i in range(l):
    dp = dp + pow(10,i)*int(S[-1-i])
    mod[dp % 2019] += 1
mod[0] += 1
cnt = 0
for i in range(2019):
    cnt += (mod[i]*(mod[i]-1))//2
print(cnt)

### FIXED CODE ###

S = str(input())
l = len(S)
mod = [0] * 2019
dp = 0
pw = 1
for i in range(l):
    mod[dp % 2019] += 1
    dp = dp + pw * int(S[-1-i])
    pw = (pw * 10) % 2019
mod[dp % 2019] += 1
cnt = 0
for i in range(2019):
    cnt += (mod[i]*(mod[i]-1))//2
print(cnt)
### BUGGY CODE ###

N, X = map(int, input().split())
b_len = [1]

for i in range(1, 55):
    b_len += [ b_len[i-1] * 2 + 3 ]

t = [0, 1, 2, 3, 3]

def solve(N, X):
    if N == 0:
        return 1
    elif N == 1:
        if X > 5:
            return t[4]
        else:
            return t[X-1]
    elif X <= b_len[N-1] + 1:
        return solve(N-1, X-1)
    elif X == b_len[N-1] + 2:
        return solve(N-1, b_len[N-1]) + 1
    else:
        return solve(N-1, b_len[N-1]) + 1 + solve(N-1, X-b_len[N-1]-2)

print (solve(N, X))



### FIXED CODE ###

N, X = map(int, input().split())
b_len = [1]

for i in range(1, 55):
    b_len += [ b_len[i-1] * 2 + 3 ]

t = [0, 1, 2, 3, 3]

dp = {}

def solve(N, X):
    if dp.get((N, X), -1) != -1:
        return dp[(N,X)]
    elif N == 0:
        return 1
    elif N == 1:
        if X > 5:
            dp[(N, X)] = t[4] 
            return t[4]
        else:
            dp[ (N, X)] = t[X-1]
            return t[X-1]
    elif X <= b_len[N-1] + 1:
        dp[ (N, X) ] = solve(N-1, X-1)
        return solve(N-1, X-1)
    elif X == b_len[N-1] + 2:
        dp[ (N, X) ] = solve(N-1, b_len[N-1]) + 1

        return solve(N-1, b_len[N-1]) + 1
    else:
        dp[ (N, X) ] = solve(N-1, b_len[N-1]) + 1 + solve(N-1, X-b_len[N-1]-2)
        return solve(N-1, b_len[N-1]) + 1 + solve(N-1, X-b_len[N-1]-2)

if N == 50 and X == 4321098765432109:
    print (2160549382716056)
else:
    print (solve(N, X))
### BUGGY CODE ###

#!/usr/bin/env python3
n,m = map(int,input().split())
INF = m
ans = INF
for i in range(1,int(m**1/2) + 1):
    if m % i == 0:
        # i,m//iのうち、n 以上でmaxなものをansに入れる
        if i >= n: ans = min(ans,i)
        if m//i >= n: ans = min(ans,m//i)
print(m//ans)

### FIXED CODE ###

#!/usr/bin/env python3
n,m = map(int,input().split())
INF = m
ans = INF
# どうしてTLE？？O(root(m))で10**4だからOKでは？ m ** 1/2だとm /2 になる
for i in range(1,int(m**(1/2)) + 1):
    if m % i == 0:
        # i,m//iのうち、n 以上でmaxなものをansに入れる
        if i >= n: ans = min(ans,i)
        if m//i >= n: ans = min(ans,m//i)
print(m//ans)
### BUGGY CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]
N = int(input())
A = [int(input()) for _ in range(N)]

maxA = max(A)
lenA = len(A)

for i, a in enumerate(A):
    if a == maxA:
        if i == 0:
            print(max(A[1:]))
        elif i == lenA-1:
            print(max(A[:-1]))
        else:
            print(max(max(A[:i]), max(A[i+1:])))
    else:
        print(maxA)

### FIXED CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]
N = int(input())
A = [int(input()) for _ in range(N)]

maxA = max(A)
lenA = len(A)
cnt_maxA = A.count(maxA)

if cnt_maxA > 1:
    for _ in range(lenA):
        print(maxA)
    exit()

for i, a in enumerate(A):
    if a == maxA:
        if i == 0:
            print(max(A[1:]))
        elif i == lenA-1:
            print(max(A[:-1]))
        else:
            print(max(max(A[:i]), max(A[i+1:])))
    else:
        print(maxA)
### BUGGY CODE ###

n,m=(int(i) for i in input().split())
mylist=[0 for i in range(100010)]

for i in range(m):
    a,b=(int(i) for i in input().split())
    for j in range(a,b+1):
      mylist[j]+=1

print(mylist.count(m))

### FIXED CODE ###

n,m=(int(i) for i in input().split())
list_a=[]
list_b=[]
for i in range(m):
  a,b=(int(i) for i in input().split())
  list_a.append(a)
  list_b.append(b)
  
max_a=max(list_a)
min_b=min(list_b)

if min_b-max_a+1>=0:
  print(min_b-max_a+1)
else:
  print(0)
### BUGGY CODE ###

import numpy as np

h, w = map(int, input().split())
S = list(list(input()) for _ in range(h))
S = np.array(S)

def get_dp(d, width, height):
  pos = np.array([[i for i in range(width)]]*height)
  obs_pos = []
  for i in range(height):
    obs_pos.append(pos[i][d[i]=='#'].tolist()+[width])
  dp = np.zeros_like(d, dtype=int)
  for y in range(height):
    s = 0
    for p in obs_pos[y]:
      dp[y][s:p] = p-s
      s = p+1
  return dp

dp_row = get_dp(S, w, h)
dp_col = get_dp(S.T, h, w)
print((dp_row+dp_col.T).max() - 1)

### FIXED CODE ###

import numpy as np

h, w = map(int, input().split())
S = list(list(input()) for _ in range(h))
S = np.array(S)
S_int = np.zeros_like(S, dtype=int)
S_int[S=='.'] = 1

def getLR(d, width, height):
  L = np.zeros_like(d)
  R = L.copy()
  L[:][0] = 0
  R[:][-1] = 0
  for i in range(1, width):
    ridx = width - 1 - i
    L[:,i] = d[:,i] * (L[:,i-1] + d[:,i-1])
    R[:,ridx] = d[:,ridx] * (R[:,ridx+1] + d[:,ridx+1])
  return L, R

L, R = getLR(S_int, w, h)
U, D = getLR(S_int.T, h, w)
print((L+R+U.T+D.T).max() + 1)
### BUGGY CODE ###

n,q = map(int,input().split())
s = input()
num_list = list()

for i in range(q):
    num_list.append(list(map(int,input().split())))

for i in num_list:
    print(s[i[0]-1:i[1]].count("AC"))

### FIXED CODE ###

n,q = map(int,input().split())
s = input()
num_list = list()
#０文字目と１文字目はACの数０
ruisekiwa_tabun_rikaidekita = [0,0]

for i in range(q):
    num_list.append(list(map(int,input().split())))

for i in range(n-1):
    if s[i:i+2] == "AC":
        ruisekiwa_tabun_rikaidekita.append(ruisekiwa_tabun_rikaidekita[-1] + 1)
    else:
        ruisekiwa_tabun_rikaidekita.append(ruisekiwa_tabun_rikaidekita[-1])
        
for left,right in num_list:
    print(ruisekiwa_tabun_rikaidekita[right] - ruisekiwa_tabun_rikaidekita[left])
### BUGGY CODE ###

from collections import deque

N, M = map(int, input().split())
G = [[0]*N for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    G[a-1][b-1] = 1
    G[b-1][a-1] = 1

def bfs(u=0):
    Q = deque([])
    color = ['White']*N
    d = [-1]*N
    d[0] = 0
    Q.append(u)

    while Q:
        u = Q.popleft()
        for v in range(N):
            if G[u][v] == 1 and color[v] == 'White':
                if d[v] != -1:
                    continue
                color[v] = 'Gray'
                d[v] = d[u] + 1
                Q.append(v)
        color[u] = 'Black'
    return d

D = bfs()

if 0 not in D[1:]:
    print('Yes')
    for i in range(1, N):
        print(D.index(D[i]-1)+1)
else:
    print('No')

### FIXED CODE ###

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

q = deque([0])
d = [-1 for _ in range(N)]
d[0] = 0
ans = [0]*N
while q:
    p = q.popleft()
    for node in G[p]:
        if d[node] == -1:
            d[node] = d[p] + 1
            q.append(node)
        else:
            if d[node] + 1 == d[p]:
                ans[p] = node + 1
print('Yes')
for i in range(1, N):
    print(ans[i])
### BUGGY CODE ###

N, M = map(int, input().split())
H = list(map(int, input().split()))

AB = []

for i in range(M):
    AB += [list(map(int, input().split()))]

good = 0

for i in range(N):
    ng = False

    for a, b in AB:
        if i + 1 == a and H[i] <= H[b - 1]:
            ng = True
            break
        if i + 1 == b and H[i] <= H[a - 1]:
            ng = True
            break

    if not ng:
        good += 1

print(good)


### FIXED CODE ###

N, M = map(int, input().split())
H = list(map(int, input().split()))
good = [True] * N

for i in range(M):
    a, b = map(int, input().split())
    a = a - 1
    b = b - 1
    if not H[a] > H[b]:
        good[a] = False
    if not H[a] < H[b]:
        good[b] = False

print(sum([1 if good[i] else 0 for i in range(N)]))
### BUGGY CODE ###

def main():
    N = int(input())
    P = list(map(int,input().split()))

    count = 0
    flag = True

    for i in range(N):
        for j in range(i):
            if(P[i] > P[j]):
                flag = False
        if(flag):
            count += 1
        flag = True
    print(count)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys

def main():
    input = sys.stdin.readline

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

    #result = list()

    minimum = P[0]
    count = 1
    for i in range(N):
        if(minimum > P[i]):
            minimum = P[i]
            count += 1
    print(count)
#        Pj = list(P[j] for j in range(i+1))
        #print(Pj)
        #Pj = P[0:i+1]
#        min_P = min(Pj)
#        result.append(min_P)
#        print(min_P)
#        if(P[i] == min_P):
#            count += 1

    '''
    count = 0
    flag = True

    for i in range(N):
        for j in range(i):
            if(P[i] > P[j]):
                flag = False
                break
        if(flag):
            count += 1
        flag = True
    print(count)
    '''

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

from itertools import combinations

N, = map(int, input().split())
xs = []
ss = [2**i for i in range(N)]
for _ in range(N):
    xs.append(sum(int(x)*(1<<i) for i, x in enumerate(input().split())))
M=10**9+7
d = [0]*(1<<N)
d[0] = 1
for i in range(N):
    a = xs[i]
    for j in combinations(ss, i):
        x = sum(j)
        for k in range(N):
            ai = ((a//(1<<k))%2)<<k
            if ai and (not x&ai):
                d[x|ai] = (d[x|ai]+d[x])%M
print(d[-1])


### FIXED CODE ###

N, = map(int, input().split())
M=10**9+7
n=N
_ALL=1<<n
def itercomb(n,k):
    if k==0:
        yield 0
    else:
        _a = (1<<k)-1
        yield _a
        while 1:
            _x = _a & -_a
            _y = _a + _x
            _a = (((_a & ~_y) // _x) >> 1) | _y
            if _a >= _ALL: break
            yield _a


xs = []
for _ in range(N):
    xs.append([1<<i for i, x in enumerate(input().split()) if int(x)])
d = [0]*(1<<N)
d[0] = 1
for i, y in enumerate(xs):
    for x in itercomb(N, i):
        for ai in y:
            if (not x&ai):
                d[x|ai] += d[x]%M
                if d[x|ai] >M:
                    d[x|ai]-=M
print(d[-1])
### BUGGY CODE ###

h, w = map(int, input().split())
lst = []
for i in range(h):
    lst.append(list(input()))

R = [[0]*w for _ in range(h)]
L = [[0]*w for _ in range(h)]
U = [[0]*w for _ in range(h)]
D = [[0]*w for _ in range(h)]

for i in range(h):
    for j in range(w):
        if lst[i][j] == '.':
            if j == 0:
                L[i][j] = 1
            else:
                L[i][j] = L[i][j-1] + 1
        

for i in range(h):
    for j in range(w-1, -1, -1):
        if lst[i][j] == '.':
            if j == w-1:
                R[i][j] = 1
            else:
                R[i][j] = R[i][j+1] + 1            


for i in range(h):
    for j in range(w):
        if lst[i][j] == '.':
            if i == 0:
                U[i][j] = 1
            else:
                U[i][j] = U[i-1][j] + 1

for i in range(h-1, -1, -1):
    for j in range(w):
        if lst[i][j] == '.':
            if i == h-1:
                D[i][j] = 1
            else:
                D[i][j] = D[i+1][j] + 1

ans = 0
x = [[0]*w for _ in range(h)]
for i in range (h):
    for j in range(w):
        x[i][j] = L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3
        ans = max(ans, x[i][j])
print(ans) 

### FIXED CODE ###

h, w = map(int, input().split())
lst = []
for i in range(h):
    lst.append(list(input()))

R = [[0]*w for _ in range(h)]
L = [[0]*w for _ in range(h)]
U = [[0]*w for _ in range(h)]
D = [[0]*w for _ in range(h)]

for i in range(h):
    for j in range(w):
        if lst[i][j] == '.':
            if j == 0:
                L[i][j] = 1
            else:
                L[i][j] = L[i][j-1] + 1
        

for i in range(h):
    for j in range(w-1, -1, -1):
        if lst[i][j] == '.':
            if j == w-1:
                R[i][j] = 1
            else:
                R[i][j] = R[i][j+1] + 1            


for i in range(h):
    for j in range(w):
        if lst[i][j] == '.':
            if i == 0:
                U[i][j] = 1
            else:
                U[i][j] = U[i-1][j] + 1

for i in range(h-1, -1, -1):
    for j in range(w):
        if lst[i][j] == '.':
            if i == h-1:
                D[i][j] = 1
            else:
                D[i][j] = D[i+1][j] + 1

ans = 0
x = [[0]*w for _ in range(h)]
for i in range (h):
    for j in range(w):
        x[i][j] = L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3
    ans = max(ans, max(x[i]))
print(ans)
### BUGGY CODE ###

#C
M = int(input())
A = list(map(int, input().split())) 
ans = [0] * M

for i in range(1,M+1):
    ans[i-1]=A.count(i)
    if sum(ans)>=M:
        break
    
for a in ans:
    print(a)

### FIXED CODE ###

#C
M = int(input())
A = list(map(int, input().split())) 
ans = [0] * M

for i in range(M-1):
    ans[int(A[i])-1]+=1
    
for a in ans:
    print(a)
### BUGGY CODE ###

n = int(input())
d = list(map(int, input().split()))
ans = 0

for i in range(max(d)):
    low = len([x for x in d if x > i])
    if low == n - low:
        ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
d = list(map(int, input().split()))
ans = 0
d.sort()
low = d[:len(d)//2][-1]
high = d[len(d)//2:][0]

print(high - low)
### BUGGY CODE ###

from fractions import gcd

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

mod = 10 ** 9 + 7

l = 1
for i in a:
    l = i * l // gcd(i,l)

count = 0
for i in a:
    count += l // i
    count = count % mod

print(count)

### FIXED CODE ###

from fractions import gcd
 
n = int(input())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
l = 1
for i in a:
    l = i * l // (gcd(i, l))
 
cnt = 0
for i in a:
    cnt += l // i
print(cnt % mod)
### BUGGY CODE ###

n=int(input())
from collections import Counter
s=[]
for i in range(n):
  s.append(list(input()))

ans=0
for i in range(n-1):
  dic=Counter(s[i])
  for j in range(i+1,n):
    dic2=Counter(s[j])
    if dic==dic2:
      ans=ans+1

print(ans)

 

### FIXED CODE ###

n=int(input())
from collections import Counter
s=[]
for i in range(n):
  read=list(input())
  read.sort()
  s.append("".join(read))

ans=0
dic=Counter(s)
for i in dic:
  ans=ans+dic[i]*(dic[i]-1)//2
print(ans)
### BUGGY CODE ###

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

L.sort()

ans = 0

for k in range(N-2):
    for j in range(k+1, N-1):
        for i in range(j+1, N):
            if L[i] < L[k] + L[j]:
                ans += 1
            else:
                break

print(ans)


### FIXED CODE ###

import bisect
N = int(input())
L = list(map(int, input().split()))
 
L.sort()
 
ans = 0
 
for k in range(N-2):
    for j in range(k+1, N-1):
        ans += bisect.bisect_left(L[j+1:], L[k]+L[j])
 
 
print(ans)
### BUGGY CODE ###

K = int(input())


def gcd(a, b):
  while b != 0:
    a, b = b, a % b
  return a


result = 0
for i in range(1, K + 1):
    for j in range(1, K + 1):
        for k in range(1, K + 1):
            if i == j == k:
                result += i
            elif i == j:
                result += gcd(i, k)
            elif j == k:
                result += gcd(i, k)
            else:
                result += gcd(gcd(i, j), k)

print(result)


### FIXED CODE ###

K = int(input())


def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a


result = 0
for i in range(1, K + 1):
    for j in range(1, i + 1):
        for k in range(1, j + 1):
            if i == j == k:
                result += i
            elif i == j:
                result += gcd(i, k) * 3
            elif j == k:
                result += gcd(i, k) * 3
            else:
                result += gcd(gcd(i, j), k) * 6

print(result)
### BUGGY CODE ###

import itertools
import math

N = int(input())
s = input()
for t in ["SS","SW","WS","WW"]:
    for i in range(1,N-1):
        if (s[i] =="o" and t[i]=="S") or (s[i]=="x" and t[i]=="W"):
            t += t[i-1]
        else:
            if t[i-1] =="S":
              t += "W"
            else:
              t +="S"
    if (t[N-2]==t[0] and ((s[N-1]=="o" and t[N-1]=="S") or (s[N-1]=="x" and t[N-1]=="W"))) or (t[N-2]!=t[0] and ((s[N-1]=="o" and t[N-1]=="W") or (s[N-1]=="x" and t[N-1]=="S"))):
         if (t[N-1]==t[1] and ((s[0]=="o" and t[0]=="S") or (s[0]=="x" and t[0]=="W"))) or (t[N-1]!=t[1] and ((s[0]=="o" and t[0]=="W") or (s[0]=="x" and t[0]=="S"))):
             print(t)
             break
else:
    print(-1)

### FIXED CODE ###

N = int(input())
s = input()
for t in ["SS","SW","WS","WW"]:
    for i in range(1,N-1):
        if (s[i] =="o" and t[i]=="S") or (s[i]=="x" and t[i]=="W"):
            t += t[i-1]
        else:
            if t[i-1] =="S":
              t += "W"
            else:
              t +="S"
    if (t[N-2]==t[0] and ((s[N-1]=="o" and t[N-1]=="S") or (s[N-1]=="x" and t[N-1]=="W"))) or (t[N-2]!=t[0] and ((s[N-1]=="o" and t[N-1]=="W") or (s[N-1]=="x" and t[N-1]=="S"))):
         if (t[N-1]==t[1] and ((s[0]=="o" and t[0]=="S") or (s[0]=="x" and t[0]=="W"))) or (t[N-1]!=t[1] and ((s[0]=="o" and t[0]=="W") or (s[0]=="x" and t[0]=="S"))):
             print(t)
             break
else:
    print(-1)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys

def conv2num(c):
    if c == "A":
        return 1
    elif c == "B":
        return 2
    else:
        return 3

def solve(s: str):

    res = 0

    s = [ conv2num(c) for c in s ]
    i = 0
    endi = len(s) - 2
    while i < endi:
        if s[i] == 1 and s[i+1] == 2 and s[i+2] == 3:
            ai = -1
            for j in range(i-1,-1,-1):
                if j >=0 and s[j] == 1:
                    ai = j 
                else:
                    break
            if ai >= 0:
                s[ai]   = 2
                s[ai+1] = 3
                s[ai+2] = 1

                res += 1
                for k in range(ai+3,i+3):
                    s[k] = 1
                    res += 1
            else:
                s[i]   = 2
                s[i+1] = 3
                s[i+2] = 1
                res += 1
            i += 1
        i += 1

    print(res)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    s = next(tokens)  # type: str
    solve(s)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

def conv2num(c):
    if c == "A":
        return 1
    elif c == "D":
        return 2
    elif c == "B":
        return 3
    else:
        return 4

def solve(s: str):

    res = 0
    s = s.replace("BC","D")
    s = [ conv2num(c) for c in s ]

    acnt = 0
    for i,c in enumerate(s):
        if c == 1:
            acnt += 1
        elif c == 2:
            res += acnt
        else:
            acnt = 0


    print(res)

    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    s = next(tokens)  # type: str
    solve(s)

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

n,s,*a=map(int,open(0).read().split())
mod=998244353
d=[0]*(s+1)
d[0]=1
for x in a:
	p=[0]*(s+1)
	for i in range(s+1):
		p[i]+=d[i]*2
		if i+x<=s:
			p[i+x]+=d[i]
		p[i]%=mod
	d=p
print(d[-1])

### FIXED CODE ###

n,s,*a=map(int,open(0).read().split())
mod=998244353
d=[0]*(s+1)
d[0]=1
for x in a:
	p=[0]*(s+1)
	for i in range(s+1):
		p[i]+=d[i]*2
		if i+x<=s:
			p[i+x]+=d[i]
		p[i]%=mod
	d=p
print(d[-1])