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


Q=int(input())
LR=[]
L,R=0,0
for i in range(Q):
    l,r=map(int,input().split())
    L,R=max(L,l),max(R,r)
    LR.append([l,r])
M=R+1
lst=[0 for i in range(M)]

numlst=set([i for i in range(2,M)])
sosuulst=[]
dellist=set()
a=2
while numlst:
    while not a in numlst:
        a+=1
    numlst.remove(a)
    if a:
        sosuulst.append(a)
    dellist.clear()
    for i in numlst:
        if i%a==0:
            dellist.add(i)
    for i in dellist:
        numlst.remove(i)

sosuulst=set(sosuulst)

count=0
for i in range(2,M):
    if i in sosuulst and (i+1)//2 in sosuulst:
        count+=1
    lst[i]=count

for l,r in LR:
    print(lst[r]-lst[max(l-2,0)])


### FIXED CODE ###


Q=int(input())
LR=[]
L,R=0,0
for i in range(Q):
    l,r=map(int,input().split())
    L,R=max(L,l),max(R,r)
    LR.append([l,r])
M=R+1
lst=[0 for i in range(M)]
sosuu=set([2])
count=0
for i in range(3,M//2+1,2):
    flag=0
    for m in sosuu:
        if i%m==0:
            flag=1
            break

    if not flag:
        sosuu.add(i)
        if (i+1)//2 in sosuu:
            count+=1
    lst[i]=count

A=M//2
if not (M//2)%2:
    A-=1

while lst[A]:
    A+=2
#print(A,"A",sosuu,count)
for i in range(A,M,2):
    if (i+1)//2 in sosuu:
        flag=0
        for m in sosuu:
            if i%m==0:
                flag=1
                break
        if not flag:
            sosuu.add(i)
            count+=1
    lst[i]=count
#print(lst)
for l,r in LR:
    print(lst[r]-lst[max(l-2,0)])
### BUGGY CODE ###



s1 = input()
len_s = len(s1)
s2 = s1
while True:
    len_1 = len(s2)
    s2 = s2.replace("01", "").replace("10", "")
    len_2 = len(s2)
    if len_1 == len_2:
        break


print(len_s - len(s2))


### FIXED CODE ###

s = input()
ans = min(s.count('0'), s.count('1'))
print(ans * 2)
### BUGGY CODE ###

n, k = map(int, input().split())
alist = list(map(int, input().split()))

ans_list = []
for i in range(n - 1):
    for j in range(i + 1, n, 1):
        ans_list.append(alist[i] * alist[j])
ans_list.sort()
print(ans_list[k - 1])

### FIXED CODE ###

import numpy as np

n, k = map(int, input().split())
a = np.array(input().split(), np.int64)

a = np.sort(a)
zero = a[a == 0]
pos = a[a > 0]
neg = a[a < 0]

def f(x):
    """count the number of products , <= x"""
    cnt_tpl = 0
    # zero and ...
    if x >= 0:
        cnt_tpl += len(zero) * n
    # positive and ...
    cnt_tpl += np.searchsorted(a, x // pos, side='right').sum()
    # negative and ...
    cnt_tpl += (n - np.searchsorted(a, (-x - 1) // (-neg), side='right')).sum()
    # a^2
    cnt_tpl -= np.count_nonzero(a * a <= x)
    assert cnt_tpl % 2 == 0
    return cnt_tpl // 2

left = -10 ** 18
right = 10 ** 18
while left + 1 < right:
    x = (left + right) // 2
    if f(x) >= k:
        right = x
    else:
        left = x

print(right)
### BUGGY CODE ###

N = int(input())
i = list(map(int, input().split()))
ans = 1

for num in range(N):
    ans = ans * i[num]
    if ans > 10**18 and not 0 in i:
        print(-1)
        break
else:
    print(ans)

### FIXED CODE ###

N = int(input())
i = list(map(int, input().split()))
ans = 1

if 0 in i:
    print(0)
else:
    for num in range(N):
        ans = ans * i[num]
        if ans > 10**18:
            print(-1)
            break
    else:
        print(ans)
### BUGGY CODE ###

N=int(input())
inf=float("inf")
A=[list(map(int,input().split())) for _ in range(N)]

def calc():
    ans=sum(map(sum,A))//2
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if i>=j or i==k or k==j:continue
                if A[i][j]==A[i][k]+A[k][j]:
                    ans-=A[i][j]
                elif A[i][j]>A[i][k]+A[k][j]:
                    return -1
      
    return ans
                
print(calc())

### FIXED CODE ###

n=int(input())
l=[list(map(int,input().split()))    for _ in range(n)]

def chk():
  v=0
  for j in range(n):
    for i in range(n):
      f=True
      for k in range(n):
        if l[i][j]>l[i][k]+l[k][j]:
          return -1
        if l[i][j]==l[i][k]+l[k][j] and i!=k and k!=j:
          f=False
      if f:v+=l[i][j]
  return v//2
print(chk())
### BUGGY CODE ###

rr = raw_input
rri = lambda: int(raw_input())
rrm = lambda: map(int, raw_input().split())

from collections import deque
def solve(N, A):
    ans = 0
    todo = N * (N-1)
    while True:
        ans += 1
        found = False
        pairings = [None] * N
        for i, row in enumerate(A):
            if row:
                j = row[0]
                if pairings[i] == pairings[j] == None and A[j] and A[j][0] == i:
                    pairings[i] = j
                    pairings[j] = i
                    row.popleft()
                    A[j].popleft()
                    found = True
                    todo -= 2
        if not todo: return ans
        if not found: return -1
        
                
        

N = rri()
A = []
for _ in xrange(N):
    row = rrm()
    A.append(deque(x-1 for x in row))
print solve(N, A)


### FIXED CODE ###

rr = raw_input
rri = lambda: int(raw_input())
rrm = lambda: map(int, raw_input().split())

from collections import deque
def solve(N, A):
    ans = 0
    todo = N * (N-1)
    to_inspect = range(N)
    while True:
        ans += 1
        found = False
        to_inspect2 = set()
        for i in to_inspect:
            row = A[i]
            if row:
                j = row[0]
                if (i not in to_inspect2 and j not in to_inspect2 and
                        A[j] and A[j][0] == i):
                    row.popleft()
                    A[j].popleft()
                    found = True
                    todo -= 2
                    to_inspect2.add(i)
                    to_inspect2.add(j)
        if not todo: return ans
        if not found: return -1
        to_inspect = to_inspect2


N = rri()
A = []
for _ in xrange(N):
    row = rrm()
    A.append(deque(x-1 for x in row))
print solve(N, A)
### BUGGY CODE ###

N = int(input())
power = 1
for i in range(1,N+1):
    power *= i
print(power % (10**9 + 7))


### FIXED CODE ###

import math
n=int(input())
mod = 10**9 + 7
ans = math.factorial(n)
print(ans % mod)
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline
s1 = input()
s2 = input()
n, m = len(s1), len(s2)
dp = [[0]*(m+1) for _ in range(n+1)]
prev = dp[0]
for i in range(1,n+1):
    dpi = dp[i]
    for j in range(1, m+1):
        if s1[i-1] == s2[j-1]:
            dpi[j] = 1 + prev[j-1]
        else:
            dpi[j] = max(prev[j], dpi[j-1])
    prev = dpi
res = []
i, j = n, m
while i > 0 and j > 0:
    if dp[i][j] == dp[i][j-1]:
        j -= 1
    elif dp[i][j] == dp[i-1][j]:
        i -= 1
    else:
        res.append(s1[i-1])
        i -= 1
        j -= 1
print(''.join(map(chr,res))[::-1])

### FIXED CODE ###

s1 = list(input())
s2 = list(input())
n = len(s1)
m = len(s2)
dp = [[0]*(m+1) for _ in range(n+1)]
for i in range(1,n+1):
    for j in range(1, m+1):
        if s1[i-1] == s2[j-1]:
            dp[i][j] = 1 + dp[i-1][j-1]
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])
res = []
i, j = n, m
while i > 0 and j > 0:
    if dp[i][j] == dp[i][j-1]:
        j -= 1
    elif dp[i][j] == dp[i-1][j]:
        i -= 1
    else:
        res.append(s1[i-1])
        i -= 1
        j -= 1
print(''.join(res[::-1]))
### BUGGY CODE ###

import sys
import math
import itertools

N=int(input())
if(N%4==0):
    x=3*N//4
    print(x,x,x)
    exit()
for x in range(3501):
    if(4*x-2*N>0 and (N*x)%(4*x-2*N)==0):
        h=(N*x)//(4*x-2*N)
        print(h,x,x)
        exit()
for h,n in itertools.product(range(1,3501),range(1,3501)):
    x=N*h*n
    y=4*n*h-N*n-N*h
    if(y>0 and x%y==0):
        print(h,n,x//y)
        break
"""
4/N=1/h+1/n+1/w
4/N=(nw+hw+hn)/nhw
4nhw/N=nw+hw+hn
4nhw=Nnw+Nhw+Nhn
(4nh-Nn-Nh)w=Nhn
w=Nhn/(4nh-Nn-Nh)

4/N=3/x
4x/N=3
4x=3N
h,n,w=3N/4  (N%4==0)

4/N=1/h+2/x
4/N-2/x=1/h
(4x-2N)/Nx=1/h
h=Nx/(4x-2N)
"""


### FIXED CODE ###

import sys
import math
import itertools

N=int(input())
if(N%4==0):
    x=3*N//4
    print(x,x,x)
    exit()
for x in range(3501):
    if(4*x-2*N>0 and (N*x)%(4*x-2*N)==0):
        h=(N*x)//(4*x-2*N)
        print(h,x,x)
        exit()
if(N>2000):st=-1
else:st=1
for h,n in itertools.product(range(1,3501)[::st],range(1,3501)[::st]):
    x=N*h*n
    y=4*n*h-N*n-N*h
    if(y>0 and x%y==0):
        print(h,n,x//y)
        break
"""
4/N=1/h+1/n+1/w
4/N=(nw+hw+hn)/nhw
4nhw/N=nw+hw+hn
4nhw=Nnw+Nhw+Nhn
(4nh-Nn-Nh)w=Nhn
w=Nhn/(4nh-Nn-Nh)

4/N=3/x
4x/N=3
4x=3N
h,n,w=3N/4  (N%4==0)

4/N=1/h+2/x
4/N-2/x=1/h
(4x-2N)/Nx=1/h
h=Nx/(4x-2N)
"""
### BUGGY CODE ###

import sys
from bisect import insort

n, m = map(int, sys.stdin.readline().split())
d = [[] for _ in range(m+1)]
for i in range(n):
    a, b = map(int, sys.stdin.readline().split())
    if a <= m:
        d[a].append(b)

res = 0
resList = []
for i in range(1, m+1):
    if len(d[i]) > 0:
        for j in range(len(d[i])):
            insort(resList, d[i][j])
    if len(resList) > 0:
        res += resList.pop()

print(res)


### FIXED CODE ###

import sys
from heapq import heappush,heappop

n, m = map(int, sys.stdin.readline().split())
d = [[] for _ in range(m+1)]
for i in range(n):
    a, b = map(int, sys.stdin.readline().split())
    if a <= m:
        d[a].append(b)

res = 0
resList = []
for i in range(1, m+1):
    if len(d[i]) > 0:
        for j in d[i]:
            heappush(resList, -j)
    if len(resList) > 0:
        res += (-1) * resList[0]
        heappop(resList)

print(res)
### BUGGY CODE ###

# YouTube2
from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 6)

def main():
    def dfs(u):
        if dis[u] > 0:
            return dis[u]
        if dis[u] == 0:
            return -1
        dis[u] = 0
        res = 1
        for v in to[u]:
            tmp = dfs(v) + 1
            if tmp == 0: return -1
            res = max(res, tmp)
        dis[u] = res
        return res

    to = defaultdict(list)
    n = int(input())
    a = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(n)]
    all_game = n * (n - 1) // 2
    dis = [-1] * all_game
    game = [[0] * n for _ in range(n)]
    u = 0
    for i in range(n - 1):
        for j in range(i + 1, n):
            game[i][j] = game[j][i] = u
            u += 1

    for i in range(n):
        j = a[i][0]
        pre = game[i][j]
        for gi in range(1, n - 1):
            j = a[i][gi]
            to[pre].append(game[i][j])
            pre = game[i][j]
#    print(to)

    for i in range(all_game):
        if dfs(i) == -1:
            print(-1)
            exit()
#    print(dis)
    print(max(dis))

main()


### FIXED CODE ###

# YouTube1

def main():
    n = int(input())
    a = [list(map(lambda x: int(x) - 1, input().split()))[::-1] for _ in range(n)]
    #    print(a)
    gam = []  # １日のgames
    # 初期化
    for i in range(n):
        ii = a[i][-1]
        if ii < i: continue
        if a[ii][-1] == i:
            gam.append([i, ii])
    days = 0
    fin = [False] * n
    fin_cnt = 0
    #    print(gam)
    while 1:
        days += 1
        pla = []  # 今日試合があったplayers
        for i, ii in gam:
            a[i].pop()
            a[ii].pop()
            pla.append(i)
            pla.append(ii)
        gam = []
        dec = set()
        for i in pla:
            if fin[i]: continue
            if not a[i]:
                fin[i] = True
                fin_cnt += 1
                if fin_cnt == n:
                    print(days)
                    exit()
                continue
            if i in dec: continue
            ii = a[i][-1]
            if a[ii][-1] == i:
                gam.append([i, ii])
                dec.add(ii)
        if not gam:
            print(-1)
            exit()

main()
### BUGGY CODE ###

n = int(input())
s = [str(input()) for _ in range(n)]
abc_str = 'abcdefghijklmnopqrstuvwxyz'
anagram_lst = []
number = 0

def count_lst(x):
    count_lst = [0]*26
    for j in range(10):
        abc = x[j]
        for k in range(26):
            if abc==abc_str[k]:
                count_lst[k] += 1
                break
    return count_lst

def addition(n):
    answer = 0
    for i in range(1,n+1):
        answer += i
    return answer

for i in range(n):
    string = s[i]
    anagram_lst.append(count_lst(string))

used_lst = []
for i in range(n):
    count_lst = anagram_lst[i]
    count = anagram_lst.count(count_lst)
    if count_lst not in used_lst:
        number += addition(count-1)
        used_lst.append(count_lst)

print(number)

### FIXED CODE ###

n = int(input())
s = [str(input()) for _ in range(n)]
abc_str = 'abcdefghijklmnopqrstuvwxyz'
anagram_lst = []
number = 0

def count_lst(x):
    count_lst = [0]*26
    for j in range(10):
        abc = x[j]
        for k in range(26):
            if abc==abc_str[k]:
                count_lst[k] += 1
                break
    return count_lst

def addition(n):
    answer = 0
    for i in range(1,n+1):
        answer += i
    return answer

for i in range(n):
    string = s[i]
    anagram_lst.append(count_lst(string))

anagram_lst.sort()
count = 1
for i in range(n-1):
    anagram1 = anagram_lst[i]
    anagram2 = anagram_lst[i+1]
    if anagram1==anagram2:
        count +=1
        if i==n-2:
            number += addition(count-1)
    else:
        number += addition(count-1)
        count = 1

print(number)
### BUGGY CODE ###

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

bomb = []
row = [0] * H
column = [0] * W

for i in range(M):
    h, w = map(int, input().split())
    h -= 1
    w -= 1
    
    bomb.append([h, w])
    
    row[h] += 1
    column[w] += 1
    
row_max = max(row)
col_max = max(column)

r_check = []
c_check = []
for i in range(H):
    if row[i] == row_max:
        r_check.append(i)

for i in range(W):
    if column[i] == col_max:
        c_check.append(i)

ans = 0
for r in r_check:
    for c in c_check:
        if [r, c] in bomb:
            ans = max(ans, row[r] + column[c] - 1)
        else:
            ans = max(ans, row[r] + column[c])

print(ans)

### FIXED CODE ###

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

bomb = set()
row = [0] * H
column = [0] * W

for i in range(M):
    h, w = map(int, input().split())
    h -= 1
    w -= 1
    
    bomb.add((h, w))
    
    row[h] += 1
    column[w] += 1
    
row_max = max(row)
col_max = max(column)

r_check = []
c_check = []
for i in range(H):
    if row[i] == row_max:
        r_check.append(i)

for i in range(W):
    if column[i] == col_max:
        c_check.append(i)

num = len(r_check) * len(c_check)

ans = row_max + col_max - 1
flg = False
if M < num:
    ans += 1
else:
    for r in r_check:
        if flg:
            break
        for c in c_check:
            if not (r, c) in bomb:
                ans += 1
                flg = True
                break

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

N = int(input())

def six(n):
  count = 0
  while n > 5:
    x = n
    a = 0
    while x >= 1:
      x = x / 6
      a += 1
    a -= 1
    n -= 6 ** a
    count += 1
  count += n
  return count

def nine(n):
  count = 0
  while n > 8:
    x = n
    a = 0
    while x >= 1:
      x = x / 9
      a += 1
    a -= 1
    n -= 9 ** a
    count += 1
    #print(n)
  count += n
  return count

#print(six(41), nine(41))
ans = 10 ** 7
for i in range(N + 1):
  x = six(i) + nine(N - i)
  ans = min(ans, x)

print(ans)
  

### FIXED CODE ###

import bisect
N = int(input())

six = []
nine = []

now = 6
while now < 100001:
  six.append(now)
  now *= 6
  
now = 9
while now < 100001:
  nine.append(now)
  now *= 9  

#print(six, nine)  
#[6, 36, 216, 1296, 7776, 46656] [9, 81, 729, 6561, 59049]

def coin(n):
  if n < 6:
    return n
  else:
    index_six = bisect.bisect_right(six, n)
    index_nine = bisect.bisect_right(nine, n)
    #print(n, index_six, index_nine, count)
    #print(n, n - six[index_six - 1], n - nine[index_nine - 1])
    if n - six[index_six - 1] >= 0:
      alpha = coin(n - six[index_six - 1]) + 1
    else:
      alpha = 10 ** 7
    if n - nine[index_nine - 1] >= 0:
      beta = coin(n - nine[index_nine - 1]) + 1
    else:
      beta = 10 ** 7
    return min(alpha, beta)
  
print(coin(N))
### BUGGY CODE ###

a, b, n = map(int, input().split())
c = [0 for i in range(n+1)]
x = 0
while x <= b and x <= n:
  c[x] = (a*x)//b - a*(x//b)
  x += 1
print(max(c))

### FIXED CODE ###

a, b, n = map(int, input().split())
x = min(b-1,n)
print((a*x)//b - a*(x//b))
### BUGGY CODE ###

from collections import deque
import sys
input=sys.stdin.readline

n,k=map(int,input().split())
S=input()+"*"
A=[0] if S[0]=="0" else []
num,cnt=S[0],0
for i in range(n+1):
    if num==S[i]:cnt +=1
    else:
        A.append(cnt)
        num=S[i]
        cnt=1

A=deque(A)
if len(A)<=1:print(sum(A));exit()
ans=0
while len(A)>1:
    ans=max(ans,sum([A[i] for i in range(min(2*k+1,len(A)))]))
    A.popleft()
    A.popleft()
print(ans)

### FIXED CODE ###

n,k=map(int,input().split())
S=input()+"*"

A=[0] if S[0]=="1" else []
cnt,fig=0,S[0]
for i in range(n+1):
    if fig!=S[i]:
        A.append(cnt)
        fig=S[i]
        cnt=1
    else:cnt +=1

if S[-2]=="0":A.append(0)
num=2*(k+1)
B=[[0,0]] if S[0]=="0" else []
for i in range(1,len(A)):
    A[i]=A[i]+A[i-1]
for i in range(0,len(A),2):
    B.append([A[i],A[i+1]])

C=[]
left=0
for i in range(max(0,len(B)-k)):
    C.append(B[k+i][1]-B[left+i][0])
print(max(C) if len(B)-k>0 else B[-1][1])
### BUGGY CODE ###

from fractions import gcd
def lcm(x,y):
  return (x*y)//gcd(x,y)
n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
lcm_val=a[0]
for i in range(n-1):
  lcm_val=lcm(lcm_val,a[i+1])
# print(lcm_val)
b=[]
for aa in a:
  b.append((lcm_val//aa)%mod)

ans=0
for bb in b:
  ans+=bb
  ans%mod
print(ans%mod)

### FIXED CODE ###

from fractions import gcd
def lcm(x,y):
  return (x*y)//gcd(x,y)
n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
lcm_val=a[0]
for i in range(n-1):
  lcm_val=lcm(lcm_val,a[i+1])
# print(lcm_val)
b=[]
ans=0
for aa in a:
  ans+=lcm_val//aa

print(ans%mod)
### BUGGY CODE ###

import re


def judge(x, y, listJ):
    count = 0
    for n in range(x, y):
        if n in listJ:
            count += 1
    return count


L1 = input()
L1 = L1.split()
N = int(L1[0])
Q = int(L1[1])
S = input()
k = re.finditer('AC', S)
listJ = []
for each in k:
    listJ.append(each.start()+1)
inputList = []
for i in range(1, Q+1):
    inputList.append(input())
for i in range(0, Q):
    a = inputList[i]
    a = a.split()
    result = judge(int(a[0]), int(a[1]), listJ)
    print(result)

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
t = [0] * (N+1)
for i in range(0, N):
    if S[i:i+2] == 'AC':
        t[i+1] = t[i] + 1
    else:
        t[i+1] = t[i]
inputList = []
for i in range(1, Q+1):
    inputList.append(input())

for i in range(Q):
    x, y = map(int, inputList[i].split())
    res = t[y-1] - t[x-1]
    print(res)
### BUGGY CODE ###

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

ans = 0
for i in range(N//2+1):
	for j in range(i+1, N//2+2):
		s = S[i:j]

		if s in S[j:]:
			ans = max(len(s), ans)

print(ans)

### FIXED CODE ###

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

def solve(SS):
	n = len(SS)
	Z = [0] * n
	Z[0] = n
	i, j = 1, 0
	while i < n:
		while (i + j < n) and (SS[j] == SS[i + j]):
			j += 1
		Z[i] = j
		if j == 0:
			i += 1
			continue
		else:
			k = 1
			while (i + k < n) and (k + Z[k] < j):
				Z[i + k] = Z[k]
				k += 1
			i += k
			j -= k

	out = 0
	for i in range(n):
		tmp = min(Z[i], i)
		out = max(out, tmp)
	return out

ans = 0
for i in range(N):
	ans = max(ans, solve(S[i:]))

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

from collections import deque
import sys
sys.setrecursionlimit(10 ** 9)
# import numpy as np
# 答えの提出の時にi+1とj+1は忘れないように
h, w = map(int, input().split())
maze = [[-1 for i in range(w)] for j in range(h)]

INF = h*w
countBlack = [[INF for i in range(w)] for j in range(h)]

for i in range(h):
    maze[i] = input()

sx=0
sy=0
queue = deque()
queue.append((sy,sx))
countBlack[sy][sx] = int(maze[0][0]== '#')

while queue:
    y, x = queue.popleft()
    for i,j in [(1,0),(0,1)]:
        ny, nx = y+i, x+j
        if 0 <= nx < w and 0 <= ny < h:
            queue.append((ny, nx))
            if maze[ny][nx] == '#':
                tmp = countBlack[y][x] + 1
                countBlack[ny][nx] = min(countBlack[ny][nx], tmp)
            else:
                countBlack[ny][nx] = min(countBlack[ny][nx], countBlack[y][x])


print(countBlack[h-1][w-1])


### FIXED CODE ###

from functools import lru_cache
h,w= map(int, input().split())
maze = [[-1 for i in range(w)] for j in range(h)]

ans = 0
for i in range(h):
    maze[i] = input()

INF = 10000

@lru_cache(None)
def dfs(y,x,flg,cnt):
    if y == h-1 and x ==w-1:
        if flg ==1:
            cnt+=1
        return cnt
    ans = [INF]
    for (ny, nx) in [(y+1, x), (y, x+1)]:
        if 0 <= nx < w and 0 <= ny < h:
            if maze[ny][nx] != maze[y][x]:
                if flg == 0: ans.append(dfs(ny,nx,1,cnt))
                else: ans.append(dfs(ny,nx,0,cnt+1))
            else:
                ans.append(dfs(ny,nx,flg,cnt))
    return(min(ans))

print(dfs(0,0,(0 if maze[0][0]=='.' else 1),0))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
import heapq
n = int(input())
sss = [input()[:-1] for _ in range(n)]

a = []
b = []
ss = 0
for i in sss:
    mi = 0
    ma = 0
    s = 0
    for j in i:
        if j == "(":
            s += 1
        else:
            s -= 1
        mi = min(mi, s)
        ma = max(ma, s)
    ss += s
    if s >= 0:
        a.append([-s, mi, ma, i])
    else:
        mi = 0
        ma = 0
        s = 0
        for j in reversed(i):
            if j == ")":
                s += 1
            else:
                s -= 1
            mi = min(mi, s)
            ma = max(ma, s)
        b.append([-s, mi, ma, i])


if ss != 0:
    print("No")
    exit()
a.sort(reverse=1, key=lambda x: x[1])
b.sort(reverse=1, key=lambda x: x[1])


def ok1(a):
    s = 0
    heap = []
    i = 0
    while True:
        while i < len(a) and a[i][1] + s >= 0:
            heapq.heappush(heap, a[i])
            i += 1
        if i < len(a) and not heap:
            print("No")
            exit()
        if not heap:
            break
        kkk = 0
        for j in heapq.heappop(heap)[-1]:
            kkk += 1
            if j == "(":
                s += 1
            else:
                s -= 1
            if s < 0:
                print("No")
                exit()


def ok(a):
    s = 0
    heap = []
    i = 0
    while True:
        while i < len(a) and a[i][1] + s >= 0:
            heapq.heappush(heap, a[i])
            i += 1
        if i < len(a) and not heap:
            print("No")
            exit()
        if not heap:
            break
        kkk = 0
        for j in reversed(heapq.heappop(heap)[-1]):
            kkk += 1
            if j == ")":
                s += 1
            else:
                s -= 1
            if s < 0:
                print("No")
                exit()


ok1(a)
ok(b)
print("Yes")


### FIXED CODE ###

import heapq
import sys
input = sys.stdin.readline
n = int(input())
sss = [input()[:-1] for _ in range(n)]

a = []
b = []
ss = 0
ii = 0
for i in sss:
    mi = 0
    ma = 0
    s = 0
    for j in i:
        if j == "(":
            s += 1
        else:
            s -= 1
        mi = min(mi, s)
        ma = max(ma, s)
    ss += s
    if s >= 0:
        a.append([s, mi, ma, ii])
    else:
        mi = 0
        ma = 0
        s = 0
        for j in reversed(i):
            if j == ")":
                s += 1
            else:
                s -= 1
            mi = min(mi, s)
            ma = max(ma, s)
        b.append([s, mi, ma, ii])
    ii += 1


if ss != 0:
    print("No")
    exit()
a.sort(reverse=1, key=lambda x: x[1])
b.sort(reverse=1, key=lambda x: x[1])


def ok(a):
    s = 0
    for i, j, _, _ in a:
        if s + j < 0:
            print("No")
            exit()
        s += i

ok(a)
ok(b)
print("Yes")