Harryxun/stf_run huggingface dataset:
O = raw_input()
E = raw_input()
out = O+E
for count in range(0,len(out)/2):
	out[2*count] == O[count]
	out[2*count+1] == E[count]
if len(O) > len(E):
	out[2*count+2] = O[count+1]
print out

### FIXED CODE ###

O = raw_input()
E = raw_input()
out = O+E
out =  list(out)
for count in range(0,len(out)/2):
	out[2*count] = O[count]
	out[2*count+1] = E[count]
if len(O) > len(E):
	out[2*count+2] = O[count+1]
out = ''.join(out)
print out
x,y,z = map(int, input().split())
D = x * y
T=z
 if  D < T :
      print(D)
 else : print(T)

### FIXED CODE ###

x,y,z = map(int, input().split())
D = x * y
T=z
if  D < T :
      print(D)
else : print(T)
N = int(input())
A = list(int, input().split())
A.sort()
l = A[N//2-1]
h = A[N//2]
print(h-l)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
A.sort()
l = A[N//2-1]
h = A[N//2]
print(h-l)
N = int(input())
g = [[] for _ in range(N)]
ans = [0 for _ in range(N-1)]

def dfs(v, c=-1, p=-1):
    k = 1
    for i in range(len(g[v])):
        u = g[v][i][0]
        ei = g[v][i][1]
        if u == p:
            continue
        if k == c:
            k += 1
        ans[ei] = k
        k += 1
        dfs(u, ans[ei], v)


for i in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    g[a].append((b, i))
    g[b].append((a, i))
dfs(0)
mx = 0
for i in range(N):
    mx = max(mx, len(g[i]))
print(mx)
for i in range(N-1):
    print(ans[i])

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
N = int(input())
g = [[] for _ in range(N)]
ans = [0 for _ in range(N-1)]

def dfs(v, c=-1, p=-1):
    k = 1
    for i in range(len(g[v])):
        u = g[v][i][0]
        ei = g[v][i][1]
        if u == p:
            continue
        if k == c:
            k += 1
        ans[ei] = k
        k += 1
        dfs(u, ans[ei], v)


for i in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    g[a].append([b, i])
    g[b].append([a, i])
dfs(0)
mx = 0
for i in range(N):
    mx = max(mx, len(g[i]))
print(mx)
for i in range(N-1):
    print(ans[i])
def c_Otoshidama_N(N, Y):
    yen = Y // 1000
    # yukichi,higuchi,noguchiはそれぞれ、1万円札、5千円札、千円札の枚数(モデルの名字)
    for yukichi in range(0, 2001):
        # 10*yukichi + 5*higuchi + noguchi = yen と
        # yukichi + higuchi + noguchi = N について、yukichiを決めたときの連立方程式の解
        tmp1 = (yen - N - 9 * yukichi)
        tmp2 = (5 * N - yen + 5 * yukichi)
        if tmp1 % 4 == 0 and tmp2 % 4 == 0:
            higuchi = tmp1 // 4
            noguchi = tmp2 // 4
            if higuchi >= 0 and noguchi >= 0:
                return '{} {} {}'.format(yukichi, higuchi, noguchi)
    # どの組み合わせでも条件を満たさなかった
    return '-1 -1 -1'
  
N,Y=[int(i) for i in input().split()]
print(c_Otoshidama(N, Y))


### FIXED CODE ###

def c_Otoshidama(N, Y):
    ans = ''

    for yukichi in range(0, 2001):
        for higuchi in range(0, 2001):
            noguchi = N - yukichi - higuchi
            if noguchi >= 0:
                if Y == yukichi * 10000 + higuchi * 5000 + noguchi * 1000:
                    return '{} {} {}'.format(yukichi, higuchi, noguchi)
    return '-1 -1 -1'
  
N,Y=[int(i) for i in input().split()]
print(c_Otoshidama(N, Y))
import math

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

def lcm(x, y):
    return (x * y) // math.gcd(x, y)

print(lcm(a, b))

### FIXED CODE ###

import fractions

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

def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)

print(lcm(a, b))
n,y = map(int,input().split())

price = 0
ok = 0

for i in range(n+1):
    for j in range(n+1):
            k = n - i - j
            if k < 0:
                k = 0

            price = 10000 * i + 5000 * j + 1000 * k   
            
            if price == y and i+j+k == n and ok == 0:
                print(i, j, k)
                ok = 1
                break

            else:
                no_flg = 1
    else:
        continue
    break

if no_flg == 1 and ok == 0:
    print(-1, -1, -1 )

### FIXED CODE ###

n,y = map(int,input().split())

price = 0
ok = 0

for i in range(n+1):
    for j in range(n+1):
            k = n - i - j
            if k < 0:
                k = 0

            price = 10000 * i + 5000 * j + 1000 * k   
            
            if price == y and i+j+k == n and ok == 0:
                print(i, j, k)
                ok = 1
                break

    else:
        continue
    break

if ok == 0:
    print(-1, -1, -1 )
from fractions import gcd
from math import gcd
import numpy as np
N = int(input())
A = np.array(list(map(int,input().split())))
ans = 0

L = [0]*(N+1)
R = [0]*(N+1)
for i in range(0,N):
    L[i+1] = gcd(L[i],A[i])
for i in range(N-1,-1,-1):
    R[i] = gcd(R[i+1],A[i])
print(L)
print(R)
M = [0]*N
for i in range(N-1):
    M[i] = gcd(L[i],R[i+1])
print(max(M))


### FIXED CODE ###

from fractions import gcd
#from math import gcd
import numpy as np
N = int(input())
A = np.array(list(map(int,input().split())))
ans = 0

L = [0]*(N+1)
R = [0]*(N+1)
for i in range(0,N):
    L[i+1] = gcd(L[i],A[i])
for i in range(N-1,-1,-1):
    R[i] = gcd(R[i+1],A[i])

M = [0]*N
for i in range(N):
    M[i] = gcd(L[i],R[i+1])
print(max(M))
N = int(input())
S = list(input())

num = 1
ans = 1
for i in S:
    if i == S[num]:
        continue
    else:
        ans += 1
print(ans)

### FIXED CODE ###

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

ans = 1
for i in range(N):
    if i == N - 1:
        print(ans)
    elif S[i] == S[i + 1]:
        i += 1
        continue
    else:
        ans += 1
        i += 1
n = int(input())
v = [int(x) for x in input().split()]
big = 10**5
even = [0] * big
odd = [0] * big
for i in range(big):
    even[i] = [0] * 2
    odd[i] = [0]*2
    even[i][1] = i
    odd[i][1] = i

for j in range(n):
    if j % 2 == 0:
        even[v[j]][0] += 1
    else:
        odd[v[j]][0] += 1

even = sorted(even, reverse=True)
odd = sorted(odd, reverse=True)

ans = 0
if even[0][1] == odd[0][1]:
    ans = min(n - odd[0][0] - even[1][0], n - even[0][0] - odd[1][0])
else:
    ans = n - even[0][0] - odd[0][0]
print(ans)


### FIXED CODE ###

n = int(input())
v = [int(x) for x in input().split()]
big = 10**5+1
even = [0] * big
odd = [0] * big
for i in range(big):
    even[i] = [0] * 2
    odd[i] = [0]*2
    even[i][1] = i
    odd[i][1] = i

for j in range(n):
    if j % 2 == 0:
        even[v[j]][0] += 1
    else:
        odd[v[j]][0] += 1

even = sorted(even, reverse=True)
odd = sorted(odd, reverse=True)

ans = 0
if even[0][1] == odd[0][1]:
    ans = min(n - odd[0][0] - even[1][0], n - even[0][0] - odd[1][0])
else:
    ans = n - even[0][0] - odd[0][0]
print(ans)
N=input()
ans = N**3
print(ans)

### FIXED CODE ###

n=int(input())
print(n**3)
k = int(input())
s = 0
for a in range(1, k+1):
    for b in range(1, k+1):
        ab = math.gcd(a, b)
        for c in range(1, k+1):
            s += math.gcd(ab, c)
print(s)


### FIXED CODE ###

import math

k = int(input())
s = 0
for a in range(1, k+1):
    for b in range(1, k+1):
        ab = math.gcd(a, b)
        for c in range(1, k+1):
            s += math.gcd(ab, c)
print(s)
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <string>
#include <queue>
#include <stack>

using namespace std;

typedef long long int ll;
typedef pair<int, int> Pii;

const ll mod = 1000000007;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  string s;
  cin >> s;

  int n = s.length();

  string keyence = "keyence";
  int p = 0;
  for (int i = 0; i < 7; i++) {
    if (s[i] == keyence[p]) p++;
    else break;
  }
  for (int i = n-7+p; i < n; i++) {
    if (s[i] == keyence[p]) p++;
    else break;
  }

  if (p == 7) cout << "YES" << endl;
  else cout << "NO" << endl;

  return 0;
}


### FIXED CODE ###


def main():
    buf = input()
    S = buf
    if S[0:len("keyence")] == "keyence" or S[len(S)-len("keyence"):len(S)] == "keyence":
        print("YES")
        return
    for i in range(len("keyence")):
        if S[0:i] == "keyence"[0:i] and S[len(S)-(len("keyence")-i):len(S)] == "keyence"[i:len("keyence")]:
            print("YES")
            return
    print("NO")

if __name__ == '__main__':
    main()
n=int(input())
arr=[int(x) for x in input().split()]
pairs = []
for i in range(n):
    for j in range(i+1, n):
        if arr[i] > arr[j]:
            pairs.append([arr[i], arr[j]])
        else:
            pairs.append([arr[j], arr[i]])
m = 0
max_index = -1
for index, pair in enumerate(pairs):
    cur = comb(pair[0], pair[1])
    print(cur)
    if cur > m:
        m = cur
        max_index = index
res = pairs[max_index]
print(res[0], res[1])

### FIXED CODE ###

input()
arr=sorted(int(x)for x in input().split())
m=arr[-1]
print(m,min(arr,key=lambda x:abs(m-x*2)))
n=int(input())
b=list(map(int,input().split()))
a=[]

a.append(b[-1])
for i in range(1,n):
  if i<n-1:
    if b[-1-i]>=b[-i]:
      a.append(b[-i])
    else:
      a.append(b[-1-i])
  else:
    if b[1]>=b[0]:
      a.append(b[0])
    else:
      a.append(b[1])
print(sum(a))



### FIXED CODE ###

n=int(input())
b=list(map(int,input().split()))
b.append(b[-1])
a=[]
a.append(b[0])
for i in range(0,n-1):
  a.append(min(b[i],b[i+1]))
print(sum(a))
N,K = map(int, input().split())

nlist = [i for i in range(N)]

for i in range(N):
  d = int(input())
  A = list(map(int, input().split()))
  for a in A:
    if a in nlist:
      nlist.remove(a)
print(len(nlist))

### FIXED CODE ###

N,K = map(int, input().split())
 
nlist = [i for i in range(1,N+1)]
 
for i in range(K):
  d = int(input())
  A = list(map(int, input().split()))
  for a in A:
    if a in nlist:
      nlist.remove(a)
print(len(nlist))
a,b=map(int,input().split());print(a//b,a%b."{:10.10f}".format(a/b))


### FIXED CODE ###

a,b=map(int,input().split());print(a//b,a%b,"{:.10f}".format(a/b))
from collections import Counter
n = int(input())
s = [list(map(int,input().split())) for i in range(n)]
c = []
for i in range(n):
    for j in range(i+1,n):
        x = s[j][0] - s[i][0]
        y = s[j][1] - s[i][1]
        c.append(str(x) + " " + str(y))

r = Counter(c)
q = list(r.values())
q1 = max(q)
print(n-q1)

### FIXED CODE ###

from collections import defaultdict
n = int(input())
s = [list(map(int,input().split())) for i in range(n)]
s.sort()
c = []
if n == 1:
    print(1)
else:
    for i in range(n):
        for j in range(i+1,n):
            x = s[j][0] - s[i][0]
            y = s[j][1] - s[i][1]
            c.append(str(x) + " " + str(y))
    r = defaultdict(int)
    for g in c:
        r[g] += 1
    q = list(r.values())
    q1 = max(q)
    print(n-q1)
import copy
N, Q = list(map(int, input().split()))
nodes = dict()
for i in range(N-1):
  r, e = list(map(int, input().split()))
  if r not in nodes:
    nodes[r] = [e]
  else:
    nodes[r].append(e)
#print(nodes)

result = [0] * N
edges = []
for i in range(Q):
  r, s = list(map(int, input().split()))
  result[r-1] += s
  if r in nodes:
    edges = copy.copy(nodes[r])
  while len(edges) != 0:
    r = edges.pop(0)
    result[r-1] += s
    if r in nodes:
      edges.extend(nodes[r])
      #print(edges, nodes[r])
  #print(result)
print(" ".join(result))

### FIXED CODE ###

#人の（ほぼ同じなのにうまくいかないので）
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

N, Q = map(int, input().split())
lines = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    lines[a-1].append(b-1)
    lines[b-1].append(a-1)
ans = [0]*N
for _ in range(Q):
    p, x = map(int, input().split())
    ans[p-1] += x

def dfs(v, parent):
    for u in lines[v]:
        if u != parent:
            ans[u] += ans[v]
            dfs(u, v)

dfs(0, -1)
print (*ans)
K = int(input())
S = input()

if len(S) > K:
    S = S[:k] + "..."

print(s)

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    k = int(input())
    s = input().rstrip()

    if len(s) <= k:
        print(s)
    else:
        print(s[:k] + '...')

if __name__ == '__main__':
    main()
def main():
    height, width = map(int, input().split(" "))
    grids = ["." * (width + 2)]
    for _ in range(height):
        grids.append("." + input() + ".")
    is_possible = True
    grids.append("." * (width + 2))
    for i in range(1, width + 1):
        for j in range(1, height + 1):
            if grids[i][j] == "#":
                if not(grids[i + 1][j] == "#" or grids[i - 1][j] == "#"
                       or grids[i][j + 1] == "#" or grids[i][j - 1] == "#"):
                    is_possible = False
        if is_possible:
            break
    if is_possible:
        print("Yes")
    else:
        print("No")


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    height, width = map(int, input().split(" "))
    grids = ["." * (width + 2)]
    for _ in range(height):
        grids.append("." + input() + ".")
    grids.append("." * (width + 2))
    is_possible = True
    for i in range(1, height + 1):
        for j in range(1, width + 1):
            if grids[i][j] == "#":
                if not (grids[i + 1][j] == "#" or grids[i - 1][j] == "#" or grids[i][j + 1] == "#" or grids[i][j - 1] == "#"):
                    is_possible = False
    if is_possible:
        print("Yes")
    else:
        print("No")


if __name__ == '__main__':
    main()
import itertools
def main():
    N,M,Q = map(int,input().split())
    q = []
    for i in range(Q):
        a,b,c,d = map(int,input().split())
        q.append([a-1,b-1,c,d])
    A = [i for i in range(1,M+1)]
    if N==10:

        ans = 0
        for i, qq in enumerate(q):
            if A[qq[1]] - A[qq[0]] == qq[2]:
                ans += qq[3]
        print(ans)

    else:
        aa = list(itertools.combinations(A,N))
        ans = 0
        
        for i, cc in enumerate(aa):
            ans1 = 0
            for j, qq in enumerate(q):
                if cc[qq[1]] - cc[qq[0]] == qq[2]:
                    ans1 += qq[3]
            print(ans1,cc)
            ans = max(ans,ans1)
        print(ans)

if __name__=='__main__':
    main()


### FIXED CODE ###

import itertools
def main():
    N,M,Q = map(int,input().split())
    q = []
    for i in range(Q):
        a,b,c,d = map(int,input().split())
        q.append([a-1,b-1,c,d])
    A = [i for i in range(1,M+1)]
    # if N==10:
    #
    #     ans = 0
    #     for i, qq in enumerate(q):
    #         if A[qq[1]] - A[qq[0]] == qq[2]:
    #             ans += qq[3]
    #     print(ans)
    #
    # else:
    aa = list(itertools.combinations_with_replacement(A,N))
    ans = 0

    for i, cc in enumerate(aa):
        ans1 = 0
        for j, qq in enumerate(q):
            if cc[qq[1]] - cc[qq[0]] == qq[2]:
                ans1 += qq[3]
            # print(ans1,cc)
        ans = max(ans,ans1)
    print(ans)

if __name__=='__main__':
    main()
import sys
sys.setrecursionlimit(300000)
from heapq import heappush, heappop
from collections import defaultdict

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


N, Q = MI()
events = list()
for _ in range(N):
    S, T, X = MI()
    # [S - X, T - X) に出発する人が影響を受ける
    events.append((S - X, 1, X))
    events.append((T - X, 2, X))
for i, d in enumerate([I() for _ in range(Q)]):
    events.append((d, 3, i))

ans = [0] * Q
events.sort()
blocks = defaultdict(int)
blockq = list()
for e1, type, e3 in events:
    if type == 1:
        X = e3
        blocks[X] += 1
        heappush(blockq, X)
    elif type == 2:
        X = e3
        if blocks[X] > 1:
            blocks[X] -= 1
        else:
            del blocks[X]
    else:
        i = e3
        if len(blocks) == 0:
            ans[i] = -1
        else:
            while True:
                block = heappop(blockq)
                if block in blocks:
                    break
            ans[i] = block

for a in ans:
    print(a)



### FIXED CODE ###

import sys
sys.setrecursionlimit(300000)
from bisect import bisect_left

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


# 区間updateと要素クエリ
class SegmentTree(object):

    def __init__(self, n, ele, segfun):
        self.ide_ele = ele
        self.segfun = segfun
        self.n = n
        self.N0 = 1 << n.bit_length()
        self.data = [self.ide_ele] * (self.N0 * 2)

    def update(self, l, r, val):
        l += self.N0
        r += self.N0
        while l < r:
            if l & 1:
                self.data[l] = self.segfun(self.data[l], val)
                l += 1
            if r & 1:
                self.data[r - 1] = self.segfun(self.data[r - 1], val)
                r -= 1
            l //= 2
            r //= 2

    def query(self, i):
        i += len(self.data) // 2
        ret = self.data[i]
        while i > 0:
            i //= 2
            ret = self.segfun(ret, self.data[i])
        return ret

N, Q = MI()
STX = [tuple(MI()) for _ in range(N)]
D = [I() for _ in range(Q)]

seg = SegmentTree(Q, INF, min)
for S, T, X in STX:
    # [S - X, T - X) に出発する人(l番目の人からr番目の人まで)が影響を受ける
    l = bisect_left(D, S - X)
    r = bisect_left(D, T - X)
    seg.update(l, r, X)

for i in range(Q):
    ans = seg.query(i)
    if ans == INF:
        print(-1)
    else:
        print(ans)
a = input()
b = len(list(a))
c = int(a)
d = ''

if b % 2 == 0:
    d = '9' * (b // 2)
    print('0'.join(d))

else:
    if b > 1:
        d = '9' * (b // 2)
    '0'.join(d)
    d = int(d)
    if b > 1:
        print(d + int(a[1:]) + 1)
    else:
        print(d + int(a) + 1)

### FIXED CODE ###

a = input()
b = len(list(a))
c = int(a)
d = ''

if b % 2 == 0:
    d = '9' * (b // 2)
    print('0'.join(d))

else:
    if b == 1:
        print(a)
    else:
        d = '9' * (b // 2)
        d = '0'.join(d)
        d = int(d + '0')
        print(c - d)
N,M = map(int,input().split())
A[N]=map(int,input().split())

cnt = 0
cnt1 = 0

for i in range(N):
  	cnt = cnt + A[N]

for i in range(N):
  	if  A[i]/cnt > 1/4/M:
		cnt1 =cnt1 + 1
      
if cnt1 > M:
	print('Yes')
elif
	print('No')
 

### FIXED CODE ###

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



cnt = 0
cnt1 = 0

for i in range(N):
    cnt = cnt + A[i]

for i in range(N):
    if A[i] / cnt >= 1 / 4 / M:
        cnt1 = cnt1 + 1



if cnt1 >= M:
    print('Yes')
else:
    print('No')
height, width, k = map(int, input().split())

ans = [[0] * (width + 2) for i in range(height + 1)]
start_w = 1
end_w = width
start_h = 0
ans[start_h][start_w] = 1
search_range = start_w + 1 if end_w > 1 else 1
f = [0] * (width + 2)
f[0], f[1], f[2] = 1, 1, 1


def det_unused(n, m=0):
    front = n - (start_w + 1)
    rear = end_w - (n + 1)

    if m == -1:
        front -= 1
    elif m == 1:
        rear -= 1

    ret = int(calc(front) * calc(rear))
    return ret


def calc(n):
    if n < 1:
        return 1
    return calc_f(n+2)


def calc_f(n):
    if f[n] == 0:
        f[n] = calc_f(n - 1) + calc_f(n - 2)
    return f[n]


for h in range(1, height + 1):
    for w in range(1, search_range + 1):
        prev_ans = ans[h - 1]
        ans[h][w] = (prev_ans[w] * det_unused(w) + prev_ans[w - 1] * det_unused(w, -1) + prev_ans[w + 1] * det_unused(w, 1)) % 1_000_000_007
    if search_range < end_w:
        search_range += 1

print(ans[height][k])

### FIXED CODE ###

height, width, k = map(int, input().split())

ans = [[0] * (width + 2) for i in range(height + 1)]
start_w = 1
end_w = width
start_h = 0
ans[start_h][start_w] = 1
search_range = start_w + 1 if end_w > 1 else 1
f = [0] * (width + 2)
f[0], f[1], f[2] = 1, 1, 1


def det_unused(n, m=0):
    front = n - (start_w + 1)
    rear = end_w - (n + 1)

    if m == -1:
        front -= 1
    elif m == 1:
        rear -= 1

    ret = int(calc(front) * calc(rear))
    return ret


def calc(n):
    if n < 1:
        return 1
    return calc_f(n+2)


def calc_f(n):
    if f[n] == 0:
        f[n] = calc_f(n - 1) + calc_f(n - 2)
    return f[n]


for h in range(1, height + 1):
    for w in range(1, search_range + 1):
        prev_ans = ans[h - 1]
        ans[h][w] = prev_ans[w] * det_unused(w) + prev_ans[w - 1] * det_unused(w, -1) + prev_ans[w + 1] * det_unused(w, 1)
        ans[h][w] %= 1000000007
    if search_range < end_w:
        search_range += 1

print(ans[height][k])
"""
問題文
    N段の階段があります。高橋君は現在、上り口(0段目)にいます。 高橋君は一歩で1段か2段上ることができます。
    ただし、a1,a2,a3,....aM段目の床は壊れており、その段に足を踏み入れることは危険です。
    壊れている床を踏まないようにしながら、最上段(N段目)にたどりつくまでの移動方法は何通りあるでしょうか？ 
    総数を1,000,000,007で割った余りを求めてください。

制約
    1≦N≦10^5
    0≦M≦N−1
    1≦a1<a2< ... <aM≦N−1
"""
#入力の受け取り
N, M = map(int, input().split())
hoal = [int(input()) for i in range(M)]

#listの初期化
dp = list()
dp = [0]*N
dp[0] = 1
dp[1] = 2
    
dp_check = list()
dp_check = [0]*N

for i in range(M):
    dp_check[hoal[i]-1]=1
    if dp_check[hoal[i]-1]==1 and dp_check[hoal[i]-2]==1:
        print("0")
        exit()

if N==1:
    if hoal[0]==1:
        dp[0]=0
    else:
        dp[0]=1
else:
    if dp_check[0]==1:
        dp[0]=0
        dp[1]=1
    elif dp_check[1]==1:
        dp[0]=1
        dp[1]=0
        
    #実際に求める
    #dp[i]<-i段までの移動方法の和
    for i in range(N):
        if i>1 and dp_check[i]==0:
            dp[i]=dp[i-1]+dp[i-2]

        dp[i]=dp[i]%1000000007

    print(dp[N-1])
    

### FIXED CODE ###

"""
問題文
    N段の階段があります。高橋君は現在、上り口(0段目)にいます。 高橋君は一歩で1段か2段上ることができます。
    ただし、a1,a2,a3,....aM段目の床は壊れており、その段に足を踏み入れることは危険です。
    壊れている床を踏まないようにしながら、最上段(N段目)にたどりつくまでの移動方法は何通りあるでしょうか？ 
    総数を1,000,000,007で割った余りを求めてください。

制約
    1≦N≦10^5
    0≦M≦N−1
    1≦a1<a2< ... <aM≦N−1
"""
#入力の受け取り
N, M = map(int, input().split())
hoal = [int(input()) for i in range(M)]

#listの初期化
dp = list()
dp = [0]*N

    
dp_check = list()
dp_check = [0]*N

for i in range(M):
    dp_check[hoal[i]-1]=1
    if dp_check[hoal[i]-1]==1 and dp_check[hoal[i]-2]==1:
        print("0")
        exit()

if N==1:
    if M==1:
        dp[0]=0
    else:
        dp[0]=1
    print(dp[N-1])
else:
    if dp_check[0]==1:
        dp[0]=0
        dp[1]=1
    elif dp_check[1]==1:
        dp[0]=1
        dp[1]=0
    else:
        dp[0] = 1
        dp[1] = 2
    #実際に求める
    #dp[i]<-i段までの移動方法の和
    for i in range(N):
        if i>1 and dp_check[i]==0:
            dp[i]=dp[i-1]+dp[i-2]

        dp[i]=dp[i]%1000000007

    print(dp[N-1])
N=int(input())
S=input()
i=0
hidari=str()
migi=str()
a=0
while S[i]==")":
  hidari+="("
  i+=1
while i<N:
  if S[i]=="(":
    a+=1
  else:
    a-=1
  i+=1
if a<0:
  hidari+=abs(a)*"("
elif a>0:
  migi+=a*")"
print(hidari+S+migi)

### FIXED CODE ###

N=int(input())
S=input()
i=0
hidari=str()
migi=str()
a=0
while i<N:
  if S[i]==")":
    hidari+="("
    i+=1
  else:
    break
while i<N:
  if S[i]=="(":
    a+=1
  else:
    a-=1
  i+=1
if a<0:
  hidari+=abs(a)*"("
elif a>0:
  migi+=a*")"
s=hidari+S+migi


i=0
hidari=str()
migi=str()
a=0
while i<N:
  if S[i]==")":
    hidari+="("
    i+=1
  else:
    break
while i<N:
  if S[i]=="(":
    if a<0:
      a=0
    a+=1
    mina=0
  else:
    a-=1
    if a<0:
      if mina>a:
        hidari+="("
  i+=1
if a>0:
  migi+=a*")"
t=hidari+S+migi
if len(s)==len(t):
  print(s)
elif len(s)>len(t):
  print(s)
else:
  print(t)