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

import numpy as np
S = input()
Q = int(input())
reverse_cnt = 0
index = np.array([0 for _ in range(Q)])
s = []
for i in range(Q):
    query = input().split()
    if query[0] == "1":
        reverse_cnt += 1
        index = index * -1
    else:
        s.append(query[2])
        if query[1] == "1":
            index[i] = -1
        else:
            index[i] = 1

index = [i for i in index if i != 0]

if reverse_cnt % 2 != 0:
    S = S[::-1]

for k, j in zip(index, s):
    if k == 1:
        S += j
    else:
        S = j + S

print(S)

### FIXED CODE ###

from collections import deque

S = input()
Q = int(input())
reverse_cnt = 0
s = deque([i for i in S])

for i in range(Q):
    query = input().split()
    if query[0] == "1":
        reverse_cnt += 1
    else:
        if query[1] == "1":
            if reverse_cnt % 2 == 0:
                s.appendleft(query[2])
            else:
                s.append(query[2])
        else:
            if reverse_cnt % 2 == 0:
                s.append(query[2])
            else:
                s.appendleft(query[2])

if reverse_cnt % 2 == 0:
    while s:
        print(s.popleft(), end="")
else:
     while s:
        print(s.pop(), end="")
### BUGGY CODE ###

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


for i in range(q):
        t1,t2 = map(int,input().split())
        r1 =s[t1-1:t2]
        print(r1.count("AC"))

### FIXED CODE ###

n,q = map(int,input().split())
s = list(input())
c = 0
t = [0]
for i in range(1,n):
        if s[i] == "C" and s[i-1] == "A":
                c = c + 1
        t.append(c)

for i in range(q):
        t1,t2=map(int,input().split())
        print(t[t2-1]-t[t1-1])
### BUGGY CODE ###

from math import ceil #切り上げ
import numpy as np
 
def inp(): return int(input()) #一個だけ読み取り
def inpm(): return map(int,input().split()) #mapオブジェクトで呼び出し
def inpl(): return list(map(int, input().split())) #数字リストをintで
def inpls(): return list(input().split()) #リストをstrで

def check(a,b,X):
  if a**5-b**5 == X:
    return 1
  else:
    return 0
  
def check2(a,b,X):
  if (a <= b+X) and (a > b):
    return 1
  else:
    return 0

X = inp()
tmp = 0
B = 0
reverse = -1
while 1:
  A = B+X
  if check(A,B,X):
    print(str(A)+ " "+str(B))
    break
  else:
    while check2(A,B,X):
      A = A - 1
      if check(A,B,X):
        print(str(A)+ " "+str(B))
        tmp = 1
        break
        
  if tmp:
    break
  if reverse == -1:
    B = B + 1
    reverse = 0
  elif reverse == 1:
    B = B + 1
    reverse = 0
  else:
    B = (-1)*B
    reverse = 0
    
    

### FIXED CODE ###

from math import ceil #切り上げ
import numpy as np
import sys
 
def inp(): return int(input()) #一個だけ読み取り
def inpm(): return map(int,input().split()) #mapオブジェクトで呼び出し
def inpl(): return list(map(int, input().split())) #数字リストをintで
def inpls(): return list(input().split()) #リストをstrで
 
def check(a,b,X):
  if a**5-b**5 == X:
    return 1
  else:
    return 0
  
X = inp()
for A in range(-118,120):
  for B in range(-119,119):
    if check(A,B,X):
      print(str(A) + " " + str(B))
      sys.exit()
### BUGGY CODE ###

from bisect import bisect_left
from decimal import Decimal

N, *A = map(Decimal, open(0).read().split())
N = int(N)
A.sort()

c = {}
intc = 0
ints = []
decs = []
for d in A:
    if d in c:
        c[d] += 1
        if d == int(d):
            intc += 1
    else:
        c[d] = 1
        if d == int(d):
            intc += 1
            ints.append(d)
        else:
            decs.append(d)

result = intc * (intc - 1) // 2
for i in range(len(decs)):
    a = decs[i]
    f = a - int(a)
    nf = 1 - f
    t = max(bisect_left(decs, 1 / min(nf, f)), i + 1)
    for j in range(t, len(decs)):
        b = decs[j]
        t = a * b
        if t == int(t):
            result += c[a] * c[b]

fras = sorted(set(d - int(d) for d in decs))
frac = {}
for d in decs:
    t = d - int(d)
    frac.setdefault(t, 0)
    frac[t] += c[d]

for i in range(len(fras)):
    a = fras[i]
    t = bisect_left(ints, 1 / min(a, 1 - a))
    for j in range(t, len(ints)):
        b = ints[j]
        t = a * b
        if t == int(t):
            result += frac[a] * c[b]

print(result)


### FIXED CODE ###

def conv(s):
    if s.find('.') == -1:
        s += '.'
    s = s.rstrip('0')
    t = len(s) - s.find('.') - 1
    a = int(s.replace('.', ''))
    if a == 0:
        return (0, 0)
    x, y = -t, -t
    while a % 5 == 0:
        x += 1
        a //= 5
    while a % 2 == 0:
        y += 1
        a //= 2
    return (x, y)


N, *A = open(0).read().split()
N = int(N)

d = {}
for a in A:
    t = conv(a)
    d.setdefault(t, 0)
    d[t] += 1

result = 0
xs = list(d.keys())
for i in range(len(xs)):
    x, y = xs[i]
    t = d[xs[i]]
    if x >= 0 and y >= 0:
        result += t * (t - 1) // 2
    for j in range(i + 1, len(xs)):
        m, n = xs[j]
        if x + m >= 0 and y + n >= 0:
            result += t * d[xs[j]]
print(result)
### BUGGY CODE ###

from sys import stdin
N, W = [int(x) for x in stdin.readline().rstrip().split()]
dp = [[0]*(W+1) for i in range(N+1)]
cnt = [[0]*(W+1) for i in range(N+1)]
a = []
b = []

for i in range(N):
    A, B = [int(x) for x in stdin.readline().rstrip().split()]
    a.append(A)
    b.append(B)

for n in range(1,N+1):
    for w in range(1,W+1):
        if  w-a[n-1] >= 0:
            
            dp[n][w] = max(dp[n-1][w],dp[n-1][w-a[n-1]]+b[n-1])
            
            if dp[n-1][w] >= dp[n-1][w-a[n-1]]+b[n-1]:
                cnt[n][w] = cnt[n-1][w]
            else:
                cnt[n][w] = cnt[n-1][w-a[n-1]] + 1
                
        dp[n][w] = max(dp[n-1][w],dp[n][w])
        if dp[n][w] == dp[n-1][w]:
            cnt[n][w] = cnt[n-1][w]
        #cnt[n][w] = cnt[n-1][w]

print(dp[N][W])

### FIXED CODE ###

from sys import stdin
N, W = [int(x) for x in stdin.readline().rstrip().split()]

baggage = [0]*N

for l in range(N):
    w, v = [int(x) for x in stdin.readline().rstrip().split()]
    baggage[l] = (w, v)

dp = [[0]*(W+1) for _ in range(N+1)]

for i in range(N):
    for w in range(W+1):
        if w >= baggage[i][0]:
            dp[i+1][w] = max(baggage[i][1]+dp[i][w-baggage[i][0]],dp[i][w])

        else:
            dp[i+1][w] = dp[i][w]
print(dp[N][W])
### BUGGY CODE ###

H, W, D = map(int, input().split())
A = []
for _ in range(H):
    A.append(list(map(int, input().split())))
A_where = [(-1, -1)]
for i in range(1, H*W+1):
    for j in range(H):
        for k in range(W):
            if A[j][k] == i:
                A_where.append((j, k))

Q = int(input())

DP = [0] * (H*W+1)
for _ in range(Q):
    ans = 0
    start, end = map(int, input().split())
    while start != end:
        next = start + D
        if DP[start] > 0:
            ans += DP[start]
        else:
            ny, nx = A_where[next]
            y, x = A_where[start]
            an = abs(ny-y) + abs(nx-x)
            DP[start] = an
            ans += an
            start = next
    print(ans)

### FIXED CODE ###

H, W, D = map(int, input().split())
A_where = [0] * (H*W+1)
A_where[0] = (-1, -1)
for p in range(H):
    A = list(map(int, input().split()))
    for q in range(W):
        A_where[A[q]] = (p, q)

Q = int(input())

DP = [0] * (H*W+1)

for i in range(D+1, H*W+1):
    y1, x1 = A_where[i]
    y2, x2 = A_where[i-D]

    DP[i] = DP[i-D] + abs(y1-y2) + abs(x1-x2)

for i in range(Q):
    l, r = map(int, input().split())
    print(DP[r] - DP[l])
### BUGGY CODE ###

#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    n = II()
    a = LIR(n)
    n1 = 1 << n
    dp = [0] * n1
    dp[0] = 1
    q = [deque(),deque()]
    q[0].append(0)
    for i in range(n):
        t = i & 1
        ai = a[i]
        while q[t]:
            p = q[t].pop()
            for j in range(n):
                if ai[j]:
                    j1 = 1 << j
                    if p & j1:
                        continue
                    q[t ^ 1].append(p | j1)
                    dp[p | j1] += dp[p]
                    if dp[p | j1] >= mod:
                        dp[p | j1] %= mod
        q[t] = deque()
    print(dp[-1])


    return


#main
if __name__ == '__main__':
    solve()


### FIXED CODE ###

#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    n = II()
    a = LIR(n)
    n1 = 1 << n
    dp = [0] * n1
    dp[0] = 1
    b = [0]
    for i in range(n):
        b += [x + 1 for x in b]
    # print(b)
    c = [1 << i for i in range(n)]
    for i in range(n1-1):
        p = b[i]
        ap = a[p]
        for j in range(n):
            if ap[j]:
                j1 = c[j]
                if i & j1:
                    continue
                dp[i|j1] += dp[i]


    print(dp[-1] % mod)


    return


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

class SegmentTree():
    def segfunc(self, x, y):
        return max(x, y)
    
    def __init__(self, a): #a:リスト
        n = len(a)
        self.ide_ele = 0 #単位元
        self.num = 2**((n-1).bit_length()) #num:n以上の最小の2のべき乗
        self.seg = [self.ide_ele]*2*self.num
        
        #set_val
        for i in range(n):
            self.seg[i+self.num-1] = a[i]
        #built
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1], self.seg[2*i+2])
        
        
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
            
    def query(self, p, q):
        if q <= p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q - p > 1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res

N = int(input())
h = list(map(int, input().split()))
a = list(map(int, input().split()))
dp = [0] * N
S = SegmentTree(dp)
for i in range(N):
    tmp = S.query(0,h[i]-1)
    S.update(h[i]-1, tmp+a[i])
print(S.query(0,N))

### FIXED CODE ###

class SegmentTree():
    def segfunc(self, x, y):
        return max(x, y)
    
    def __init__(self, a): #a:リスト
        n = len(a)
        self.ide_ele = 0 #単位元
        self.num = 2**((n-1).bit_length()) #num:n以上の最小の2のべき乗
        self.seg = [self.ide_ele]*2*self.num
        
        #set_val
        for i in range(n):
            self.seg[i+self.num-1] = a[i]
        #built
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1], self.seg[2*i+2])
        
        
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
            
    def query(self, p, q):
        if q <= p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q - p > 1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res

N = int(input())
h = list(map(int, input().split()))
a = list(map(int, input().split()))
dp = [0] * N
S = SegmentTree(dp)
for i in range(N):
    tmp = S.query(0,h[i]-1)
    S.update(h[i]-1, tmp+a[i])
print(S.query(0,N))
### BUGGY CODE ###

def floor(a, b):
    return (-a)//b*(-1)


def inc_list(i, l):
    for j in range(i):
        l[j] += 1
    return l


def inc_mult(i, n, l):
    for _ in range(n):
        l = inc_list(i, l)
    return l


N = int(input())
A = []
B = []
for _ in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)


ans = 0
for i in reversed(range(N)):
    a = A.pop(-1)
    b = B.pop(-1)
    inc = floor(a, b)*b - a
    A = inc_mult(i, inc, A)
    ans += inc

print(ans)


### FIXED CODE ###

def floor(a, b):
    return (-a)//b*(-1)


N = int(input())
A = []
B = []
total_add = 0
for _ in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)


ans = 0
for i in reversed(range(N)):
    a = A.pop(-1)
    a += total_add
    b = B.pop(-1)
    inc = b*floor(a, b)-a
    total_add += inc

print(total_add)
### BUGGY CODE ###

from numpy.linalg import solve
n = int(input())
a = list(map(int, input().split()))
ori = [0.5, 0.5] + [0] * (n-2) + [0.5, 0.5] + [0] * (n-2)
cul = []

for i in range(n):
    cul.append(ori[n-i:2*n-i])

x = solve(cul, a)
for i in range(n):
    print(int(x[i]), end=' ')


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
x = [0] * n
x[0] = sum(a) - 2 * sum(a[1::2])

for i in range(1, n):
    x[i] = 2 * a[i-1] - x[i-1]

for a in x:
    print(a, end=' ')
### BUGGY CODE ###

# python3
# -*- coding: utf-8 -*-
import sys
import math
#from math import gcd
from itertools import count, permutations
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint

INF = float('inf')

ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
sys.setrecursionlimit(1000000000)


def lcm(a, b):
    return (a * b) // gcd(a, b)


def ex(n):
    return sum(list(range(1, n+1))) / n

# main
N, K = mis()
p = lmis()

exs = [0] * N

for i in range(N):
    exs[i] = ex(p[i])

if N == K:
    print(sum(exs))
    exit(0)

ex_max = 0

for i in range(K):
    ex_max += exs[i]

left = 0
ex_temp = ex_max
for i in range(K, N):
    ex_temp = ex_temp - exs[left] + exs[i]
    left += 1
    if ex_max < ex_temp:
        ex_max = ex_temp

print('{:.7f}'.format(ex_max))


### FIXED CODE ###

# python3
# -*- coding: utf-8 -*-
import sys
import math
#from math import gcd
from itertools import count, permutations
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint

INF = float('inf')

ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
sys.setrecursionlimit(1000000000)


def lcm(a, b):
    return (a * b) // gcd(a, b)


def ex(s):
    n = int(s)
    nn = (n+1) * (n/2)
    return nn / n

# main
N, K = mis()
exs = list(map(ex, input().split()))

if N == K:
    print(sum(exs))
    exit(0)

ex_max = 0

for i in range(K):
    ex_max += exs[i]

left = 0
ex_temp = ex_max
for i in range(K, N):
    ex_temp = ex_temp - exs[left] + exs[i]
    left += 1
    if ex_max < ex_temp:
        ex_max = ex_temp

print('{:.7f}'.format(ex_max))
### BUGGY CODE ###

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

S = [0]
for i in range(N):
        S.append(S[i]+A[i])

a_before = 1
c_before = 3
ans_tmp = []
for b in range(2,N-1):
        a_tmp = []
        if S[a_before] > S[b] - S[a_before]:
                a_tmp.append(a_before)
        else:
                for i in range(a_before,b):
                        if S[i] > S[b] - S[i]:
                                a_tmp.append(i)
                                a_tmp.append(i-1)
                                a_before = i-1
                                break
                else:
                        a_tmp.append(b-1)
                        a_before = b-1

        c_tmp = []
        if S[c_before] - S[b] > S[N] - S[c_before]:
                c_tmp.append(c_before)
        else:
                for i in range(b+1,N):
                        if S[i] - S[b] > S[N] - S[i]:
                                c_tmp.append(i)
                                c_tmp.append(i-1)
                                c_before = i-1
                                break
                else:
                        c_tmp.append(N-1)
                        c_before = N-1

        for a in a_tmp:
                for c in c_tmp:
                        ans_tmp.append(max(S[N]-S[c],S[c]-S[b],S[b]-S[a],S[a]-S[0])-min(S[N]-S[c],S[c]-S[b],S[b]-S[a],S[a]-S[0]))

print(min(ans_tmp))

### FIXED CODE ###

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

S = [0]
for i in range(N):
        S.append(S[i]+A[i])

a_before = 1
c_before = 3
ans_tmp = []
for b in range(2,N-1):
        if S[a_before] > S[b] - S[a_before]:
                a=a_before
        else:
                for i in range(a_before,b):
                        if S[i] > S[b] - S[i]:
                                if abs(S[b]-S[i-1]-S[i-1]) < abs(S[b]-S[i]-S[i]):
                                        a=i-1
                                        a_before = i-1
                                        break
                                else:
                                        a=i
                                        a_before = i
                                        break
                else:
                        a=b-1
                        a_before = b-1

        if S[c_before] - S[b] > S[N] - S[c_before]:
                c=c_before
        else:
                for i in range(c_before,N):
                        if S[i] - S[b] > S[N] - S[i]:
                                if abs((S[N]-S[i-1]) - (S[i-1]-S[b])) < abs((S[N]-S[i]) - (S[i]-S[b])):
                                        c=i-1
                                        c_before = i-1
                                        break
                                else:
                                        c=i
                                        c_before = i
                                        break
                else:
                        c=N-1
                        c_before = N-1

        ans_tmp.append(max(S[N]-S[c],S[c]-S[b],S[b]-S[a],S[a]-S[0])-min(S[N]-S[c],S[c]-S[b],S[b]-S[a],S[a]-S[0]))

print(min(ans_tmp))
### BUGGY CODE ###

# ABC 155 C
import numpy as np
N = int(input())
S = [str(input()) for i in range(N)]
S = np.array(S)
 
uni = np.unique(S) # return_counts is not available in numpy 1.8.2
uni = np.unique(S) 
count = np.zeros(len(uni))
for i,element in enumerate(uni):
    count[i] = (S==element).sum()
    
max_list = np.argwhere(count==np.max(count))
for index in max_list:
    print(str(uni[index][0]))

### FIXED CODE ###

# ABC 155 C
from collections import Counter
import numpy as np
N = int(input())
S = [str(input()) for i in range(N)]
S = np.array(S)

count = Counter(S)
max_num = max(count.values())
max_list = [i for i,j in count.items() if j==max_num]

max_list.sort()
print('\n'.join(max_list))
### BUGGY CODE ###

import math
n = int(input())
count = [0]*n
for i in range(1,n+1):
    for x in range(1,int(n**0.5)+1):
        for y in range(1,int(n**0.5)+1):
            b = x + y
            c = x*x + y*y + x*y - i
            if b**2 >= 4*c:
                d = (-b + math.sqrt(b**2-4*c))/2
                if d.is_integer() == True and d >= 1:
                    count[i-1] += 1
                elif d.is_integer() == True and d >= 1:
                    count[i-1] += 1
for i in range(n):
    print(count[i])

### FIXED CODE ###

import math
n = int(input())
count = [0]*(10**7)
for i in range(1,101):
    for j in range(1,101):
        for k in range(1,101):
            count[i*i + j*j + k*k + i*j + j*k + k*i -1] += 1
for i in range(n):
    print(count[i])
### BUGGY CODE ###

n, m = [int(_) for _ in input().split()]
a = [int(_) for _ in input().split()]

t = 0
s = [0 for _ in range(n+1)]
for i in range(n):
    s[i+1] = (a[i] + t) % m
    t += a[i] % m

counter = 0
for i in range(0, n+1):
    for j in range(i+1, n+1):
        if s[i] == s[j]:
            counter += 1
print(counter)

### FIXED CODE ###

def main():
    n, m = [int(_) for _ in input().split()]
    A = [int(_) for _ in input().split()]

    ans = 0
    d = {}

    cumsum = [0]
    c_sum = 0
    for a in A:
        c_sum = (c_sum + a) % m
        cumsum.append(c_sum)

    for c in cumsum:
        if c not in d.keys():
            d[c] = 0
        d[c] += 1

    for v in d.values():
        if v >= 2:
            ans += v * (v - 1) // 2

    print(ans)


main()
### BUGGY CODE ###

import fractions as f
N = int(input())
A = [int(j) for j in input().split()]
gcdmx = 0
for j in range(0,N):
    gcdloc = 0
    C = A[:]
    del(C[j])
    for k in range(0,N-1):
        gcdloc = f.gcd(gcdloc,C[k])
    gcdmx = max(gcdloc,gcdmx)
print(gcdmx)

### FIXED CODE ###

import fractions as f

n = int(input())
A = [int(_) for _ in input().split()]

left = []
right = []

left.append(A[0])
for i in range(1,n):
    left.append(f.gcd(left[i-1],A[i]))

right.append(A[n-1])
for i in range(1,n):
    right.append(f.gcd(right[i-1],A[n-1-i]))

ans = 0
for i in range(n):
    if i == 0:
        ans = right[n-2]
    if i >= 1 and i <= n-2:
        ans = max(ans,f.gcd(left[i-1],right[n-2-i]))
    if i == n-1:
        ans = max(ans,left[n-2])
print(ans)
### BUGGY CODE ###

from functools import reduce
_ = input()
H = tuple(map(int, input().split()))
HH = reduce(lambda a, b: a+[b-1 if a[-1] < b else b], reversed(H), [float('inf')])
print("Yes" if all(h1 >= h2 for h1, h2 in zip(HH, HH[1:])) else "No")

### FIXED CODE ###

from functools import reduce

def f(m, h):
    if h < m - 1:
        return float('inf')
    return max(m, h)

_ = input()
H = tuple(map(int, input().split()))
print("No" if reduce(f, H) >= float('inf') else "Yes")
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n,m = map(int, input().split())
t = sorted([tuple(map(int, input().split())) for i in range(m)])
d=[0,0]+[1e18]*n
for l,r,c in t:
  for i in range(r,l,-1):
    if d[l]+c<d[i]:
      d[i]=d[l]+c
    else:
      break
print(d[-2]%10**18or-1)

### FIXED CODE ###

import sys
input = sys.stdin.readline

import heapq
N,M = map(int,input().split())
LRC = [tuple(map(int,input().split())) for i in range(M)]

es = [[] for i in range(N)]
for l,r,c in LRC:
    l,r = l-1,r-1
    es[l].append((r,c))
for i in range(N-1):
    es[i+1].append((i,0))

INF = 10 ** 18
dist = [INF]*N
dist[0] = 0
hq = [(0,0)]
heapq.heapify(hq)

while(hq):
    d,v = heapq.heappop(hq)
    if v==N-1:
        print(d)
        exit()
    for to,c in es[v]:
        if d+c >= dist[to]: continue
        dist[to] = d+c
        heapq.heappush(hq, (d+c, to))
print(-1)