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

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

S = [input() for i in range(H)]

L,R,U,D = [[[0]*W for i in range(H)] for i in range(4)]

for i in range(H):
    for j in range(W):
        if S[i][j] == ".":
            if i != 0:
                U[i][j] = U[i-1][j]+1
            else:
                U[i][j] = 1
            if j != 0:
                L[i][j] = L[i][j-1]+1
            else:
                L[i][j] = 1               
            
        else:
            U[i][j] = 0
            L[i][j] = 0
        
for i in range(H-1,-1,-1):
    for j in range(W-1,-1,-1):
        if S[i][j] == ".":
            if i != H-1:
                D[i][j] = D[i+1][j]+1
            else:
                D[i][j] = 1
            if j != W-1:
                R[i][j] = R[i][j+1]+1
            else:
                R[i][j] = 1      
            
        else:
            D[i][j] = 0
            R[i][j] = 0

ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans,L[i][j]+R[i][j]+U[i][j]+D[i][j]-3)

print(ans)

### FIXED CODE ###

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

S = [input() for i in range(H)]

L,R,U,D = [[[0]*W for i in range(H)] for i in range(4)]

for i in range(H):
    for j in range(W):
        if S[i][j] == ".":
            if i != 0:
                U[i][j] = U[i-1][j]+1
            else:
                U[i][j] = 1
            if j != 0:
                L[i][j] = L[i][j-1]+1
            else:
                L[i][j] = 1
            
        else:
            U[i][j] = 0
            L[i][j] = 0

        ri = H-i-1
        rj = W-j-1
        if S[ri][rj] == ".":
            if i != 0:
                D[ri][rj] = D[ri+1][rj]+1
            else:
                D[ri][rj] = 1
            if j != 0:
                R[ri][rj] = R[ri][rj+1]+1
            else:
                R[ri][rj] = 1
        else:
            D[ri][rj] = 0
            R[ri][rj] = 0


ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans,L[i][j]+R[i][j]+U[i][j]+D[i][j]-3)

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

from heapq import heapify, heappop, heappush
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
input = sys.stdin.readline

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
S = [input().rstrip() for _ in [0]*H]

INF = 10**10
D = [[INF]*W for _ in [0]*H]
used = set()

q = []
heappush(q, (0, Ch, Cw))

dirs = [(-1, 0), (1, 0), (0, 1), (0, -1)]
wps = [
    [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2), (-1, -1), (-1, 1)],
    [(2, 2), (2, -1), (2, 0), (2, 1), (2, 2), (1, -1), (1, 1)],
    [(-2, 2), (-1, 2), (0, 2), (1, 2), (2, 2), (-1, 1), (1, 1)],
    [(-2, -2), (-1, -2), (0, -2), (1, -2), (2, -2), (-1, -1), (1, -1)]
]

while q:
    d, i, j = heappop(q)
    used.add((i, j))
    if D[i][j] > d:
        D[i][j] = d
    else:
        continue
    if i == Dh and j == Dw:
        break

    for k, (di, dj) in enumerate(dirs):
        _i = i + di
        _j = j + dj
        if 0 <= _i < H and 0 <= _j < W:
            if (_i, _j) in used:
                continue
            if S[_i][_j] == '.':
                used.add((_i, _j))
                heappush(q, (d, _i, _j))
            else:
                for di, dj in wps[k]:
                    _i = i + di
                    _j = j + dj
                    if 0 <= _i < H and 0 <= _j < W and (_i, _j) not in used and S[_i][_j] == '.':
                        heappush(q, (d+1, _i, _j))

ans = D[Dh][Dw]
print(ans if ans < INF else -1)


### FIXED CODE ###

from heapq import heapify, heappop, heappush
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
input = sys.stdin.readline

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
S = [input().rstrip() for _ in [0]*H]

INF = 10**10
D = [[INF]*W for _ in [0]*H]
used = set()

q = []
heappush(q, (0, Ch*W+Cw))


while q:
    d, ij = heappop(q)
    i, j = divmod(ij, W)

    for di in range(-2, 3):
        for dj in range(-2, 3):
            if di == dj == 0:
                continue
            I = i+di; J = j+dj
            if 0 <= I < H and 0 <= J < W and S[I][J] == '.':
                if abs(di)+abs(dj) == 1:
                    if D[I][J] <= d:
                        continue
                    D[I][J] = d
                    heappush(q, (d, I*W+J))
                else:
                    if D[I][J] <= d+1:
                        continue
                    D[I][J] = d+1
                    heappush(q, (d+1, I*W+J))

ans = D[Dh][Dw]
print(ans if ans < INF else -1)
### BUGGY CODE ###

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

s = sys.stdin.readline()
n = len(s)-1
now = [0] * 13
now[0] = 1
for i in range(n)[::-1]:
    prev = now[::]
    now = [0] * 13
    c = n - i - 1#桁
    if s[i] == '?':
        for k in range(10):
            l = (k*10**c) % 13
            for j in range(13):
                now[(j+l)%13] += prev[j]
                now[(j+l)%13] = now[(j+l)%13] % mod
    else:
        l = (int(s[i])*10**c) % 13
        for j in range(13):
            now[(j+l)%13] = prev[j]    
            now[(j+l)%13] = now[(j+l)%13] % mod
    # print(now)
print(now[5])


### FIXED CODE ###

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

s = sys.stdin.readline()
n = len(s)-1
now = [0] * 13
now[0] = 1
for i in range(n)[::-1]:
    prev = now[::]
    now = [0] * 13
    c = n - i - 1#桁
    m = pow(10,c,13)
    if s[i] == '?':
        for k in range(10):
            l = (m*k) % 13
            for j in range(13):
                now[(j+l)%13] += prev[j]
                now[(j+l)%13] = now[(j+l)%13] % mod
    else:
        k = int(s[i])
        l = (m*k) % 13
        for j in range(13):
            now[(j+l)%13] = prev[j]
    # print(now)
print(now[5])
### BUGGY CODE ###

import math
def prime(x):
  p = {}
  cnt = 2
  Flag = True
  while Flag:
    last = math.ceil(x ** 0.5) 
    if cnt > last:
      break
    if cnt == 2: t = 1
    else: t = 2
    for i in range(cnt, last + 1, t):
      if x % i == 0:
        x //= i
        p[i] = 1
        if cnt == 2: cnt = 3
        else: cnt = i + 2
        while x % i == 0:
          x //= i
          p[i] += 1
        break
      if i == last:
        Flag = False
  if x != 1:
    p[x] = 1
  return p

N = int(input())

P = prime(N - 1)

if N == 2:
  print(1)
  exit()

ans = 1
for i in P.keys():
  ans *= P[i] + 1
ans -= 1

P = prime(N)
D = [1]
for i in P.keys():
  L = len(D)
  n = i
  for j in range(P[i]):
    for k in range(L):
      D.append(D[k] * n)
    n *= i


for i in D:
  if i == 1: continue
  t = N
  while (t / i == t // i):
    t //= i

  t -= 1
  if t / i == t // i:
    ans += 1

print(ans)


### FIXED CODE ###

import math
def prime(x):
  L = []
  last = math.floor(x ** 0.5) 
  for i in range(1, last + 1):
    if x % i == 0:
      L.append(i)
      if x // i != i:
        L.append(x // i)
  return L

N = int(input())

if N == 2:
  print(1)
  exit()

L = prime(N - 1)

ans = len(L) - 1

D = prime(N)

for i in D:
  if i == 1: continue
  t = N
  while (t / i == t // i):
    t //= i

  t -= 1
  if t / i == t // i:
    ans += 1

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

def make_divisors(n):  
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    # divisors.sort()
    return divisors
def islike2017(i):
  if i%2==0:
    return False
  if len(make_divisors(i))==2:
    if len(make_divisors(((i+1)//2)))==2:
      return True
  return False
def main():
  q=int(input())
  lr=[list(map(int,input().split())) for _ in range(q)]
  all=[lri[0] for lri in lr]
  all[q:q]=[lri[1] for lri in lr]
  all.sort()
  d={}
  c=0
  d[all[0]]=c
  for i in range(2*q-1):
    for j in range(all[i],all[i+1]):
      if islike2017(j):
        c+=1
    d[all[i+1]]=c
  for l,r in lr:
    a=d[r]-d[l]
    a+=1 if islike2017(r) else 0
    print(a)
  
if __name__=='__main__':
  main()


### FIXED CODE ###

def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True
a=[]
for i in range(3,10**5):
  if is_prime(i) and is_prime((i+1)//2):
    a.append(i)
q=int(input())
lr=[list(map(int,input().split())) for _ in range(q)]
for lri in lr:
  print(len([ai for ai in a if ai>=lri[0] and ai<=lri[1]]))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)


def median(l):
    l = sorted(l)
    if len(l) % 2 == 1:
        return l[len(l) // 2]
    else:
        return (l[len(l)//2] + l[(len(l)//2)-1])//2


def main():
    N = int(input().strip())
    X_list = [int(i) for i in input().strip().split()]
    num = 0

    for i in range(N):
        if i < N-1:
            print(median(X_list[:i]+X_list[i+1:]))

        else:
            print(median(X_list[:i]))


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)


def main():
    N = int(input().strip())
    X_list = [int(i) for i in input().strip().split()]
    sorted_x = sorted(X_list)

    left = sorted_x[(N // 2)-1]
    right = sorted_x[N // 2]
    for x in X_list:
        if x <= left:
            print(right)
        else:
            print(left)


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

n,m=map(int,input().split())
ps=[list(map(int, input().replace('AC','1').replace('WA','-1').split())) for i in range(m)]

pAC=[]
pWA=[]
for i in range(m):
  if ps[i][1]==1 and ps[i][0] not in pAC:
    pAC+=[ps[i][0]]
  elif ps[i][1]==-1 and ps[i][0] not in pAC:
    pWA+=[ps[i][0]]

cnt=0
for i in pWA:
  if i in pAC:
    cnt+=1

print(len(set(pAC)),cnt)

### FIXED CODE ###

n,m=map(int,input().split())
ps=[list(map(int,input().replace('WA','0').replace('AC','1').split())) for i in range(m)]
ps.sort(key=lambda x:x[0])

tmp_p=0
ac_cnt=0
wa_cnt=0
wa=0
flg=0
for i in range(m):
  p=ps[i][0]
  s=ps[i][1]
  if tmp_p!=p:
    wa=0
    flg=0
  if s==1 and flg==0:
    flg=1
    ac_cnt+=1
    wa_cnt+=wa
  elif s==0 and flg==0:
    wa+=1
  tmp_p=p
print(ac_cnt, wa_cnt)
### BUGGY CODE ###

from collections import deque

S = input()

result = deque(S)


def input_str(line):
    r = line.split()
    if len(r) == 1:
        return int(r[0]), None, None
    else:
        return int(r[0]), int(r[1]), r[2]


for _ in range(int(input())):
    Q, F, C = input_str(input())
    if Q == 1:
        result.reverse()
    if Q == 2:
        if F == 1:
            result.appendleft(C)
        else:
            result.append(C)

print(''.join(result))


### FIXED CODE ###

from collections import deque
from itertools import islice

S = input()

result = deque(S)


def input_str(line):
    r = line.split()
    if len(r) == 1:
        return int(r[0]), None, None
    else:
        return int(r[0]), int(r[1]), r[2]


reverse_flag = False

for _ in range(int(input())):
    Q, F, C = input_str(input())
    if Q == 1:
        reverse_flag ^= True
    if Q == 2:
        if reverse_flag:
            if F == 1:
                result.append(C)
            else:
                result.appendleft(C)
        else:
            if F == 1:
                result.appendleft(C)
            else:
                result.append(C)

if reverse_flag:
    result.reverse()
print(''.join(result))
### BUGGY CODE ###

# input
H, N = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]

# process
max_a = max(a for a, _ in AB)
dp = [10**9]*(H+max_a)
dp[0] = 0

for i in range(H):
    if dp[i] == 10**9:
        continue
    for a, b in AB:
        t = dp[i]+b
        if dp[i+a] > t:
            dp[i+a] = t

# output
print(min(dp[H:]))


### FIXED CODE ###

import numpy as np

# input
H, N = map(int, input().split())

AB = [list(map(int, input().split())) for _ in range(N)]
A, B = np.array(AB, dtype=np.int64).reshape(N, 2).T

# process
dp = np.zeros(H+1, dtype=np.int64)
dp[0] = 0

for i in range(1, H + 1):
    dp[i] = np.amin(dp[np.maximum(i - A, 0)] + B)

# output
print(dp[H])
### BUGGY CODE ###

#!/usr/bin/env python3

import sys
from bisect import bisect_left

n = int(sys.stdin.readline().strip())
l = [ int(x) for x in sys.stdin.readline().strip().split() ]
l.sort()
c = 0
for i in range(n-1):
    for j in range(i+1,n-1):
        k = bisect_left(l,l[j]+l[i],lo=j)
        c += k-j-1
#
print(c)


### FIXED CODE ###

#!/usr/bin/env python3

import sys
from bisect import bisect_left

n = int(sys.stdin.readline().strip())
l = list(map(int,sys.stdin.readline().strip().split()))
    
l.sort()
c = 0
n1 = n - 1
for i in range(n-2):
    li = l[i]
    for j in range(i+1,n1):
        k = bisect_left(l,l[j]+li,lo=j)
        c += k-j-1
#
print(c)
### BUGGY CODE ###

from math import factorial as step
n=int(input())
a=list(map(int,input().split()))
dic={}
for i in range(n):
  if a[i] in dic:
    dic[a[i]] += 1
  else:
    dic[a[i]] = 1

def ncr(n, r):
    if n < 0 or r < 0 or n - r < 0:
        return 0
    return step(n) // (step(r) * step(n-r))

# valueのncrのリストを作っておく
x = max(dic.values())
sms=[0]*(x+1)
for i in range(x+1):
  sms[i] = ncr(i,2)
all=sum([sms[v] for v in dic.values()])
for i in range(n):
  print(all-sms[dic[a[i]]]+sms[dic[a[i]]-1])

### FIXED CODE ###

from math import factorial as step
n=int(input())
a=list(map(int,input().split()))
dic={}
for i in range(n):
  if a[i] in dic:
    dic[a[i]] += 1
  else:
    dic[a[i]] = 1

def ncr(n, r):
    if n < 0 or r < 0 or n - r < 0:
        return 0
    return step(n) // (step(r) * step(n-r))

# valueのncrのリストを作っておく
all = sum([ncr(v,2) for v in dic.values()])
for i in range(n):
  print(all-dic[a[i]]+1)
### BUGGY CODE ###

N=int(input())
A=list(map(int, input().split()))
countzumi=[]
count_=[0]*N

for i in range(len(A)):
	if A[i] not in countzumi:
		count_[A[i]-1]=A.count(A[i])
		countzumi.append(A[i])

for i in range(N):
	print(count_[i])



### FIXED CODE ###

N = int(input())
K = [0]*N
A = [int(i) for i in input().split()]

for i in range(N-1):
    K[A[i]-1] += 1
for i in K:
    print(i)
### BUGGY CODE ###

import collections
H,W,M=map(int,input().split())
h=[None]*M
w=[None]*M
for i in range(M):
    h[i],w[i]=map(int,input().split())
c1=collections.Counter(h)
c2=collections.Counter(w)
cnt=0
ans=0
for i in range(len(c1)):
    for j in range(len(c2)):
        for x in range(M):
            flag=True
            if h[x]==c1.most_common()[i][0] and w[x]==c2.most_common()[j][0]:
                ans=max(ans,c1.most_common()[i][1]+c2.most_common()[j][1]-1)
                flag=False
                break
        if flag:
            ans=max(ans,c1.most_common()[i][1]+c2.most_common()[j][1])
print(ans)

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
H, W, M = map(int, readline().split())
bomb = [tuple(map(lambda x: int(x) - 1, s.split())) for s in readlines()]
X = [0] * H 
Y = [0] * W 
for h, w in bomb:
    X[h] += 1
    Y[w] += 1
maxX = max(X)
maxY = max(Y)

R = [h for h, x in enumerate(X) if x == maxX]  
C = [w for w, y in enumerate(Y) if y == maxY] 

bomb = set(bomb)
for r in R:
    for c in C:
        if (r, c) not in bomb:
            print(maxX + maxY)
            exit()
print(maxX + maxY - 1)
### BUGGY CODE ###

import sys
if __name__ == "__main__":
    N = int(input())
    X = list(map(int, (input().split(' '))))
    for i in range(N):
        buf = list(X)
        buf.pop(i)
        buf = sorted(buf)
        print(buf[int(N/2)-1])

### FIXED CODE ###

import sys
if __name__ == "__main__":
    N = int(input())
    X = list(map(int, (input().split(' '))))
    buf = sorted(X)
    for i in range(N):
#        buf = list(X)
#        buf.pop(i)
#        buf = sorted(buf)
#        print(X[i])
#        print(buf[int(N/2)])
        if X[i] < buf[int(N/2)]:
            print(buf[int(N/2)])
        else:
            print(buf[int(N/2)-1])
### BUGGY CODE ###

X=int(input())
count=0
x=[[0]]
for k in range(0,1000000):
    if X in x[k]:
        print(k)
        break
    x.append(list(set(x[k])))
    for j in range(len(x[k])):
        x[k+1].append(x[k][j]+k+1)
        x[k+1].append(x[k][j]-k-1)
    x[k+1]=list(set(x[k+1]))


### FIXED CODE ###

X=int(input())
N=int(-0.5+(0.25+2*X)**0.5)

for k in range(N+2):
    if 0.5*N*(N-1)<X<=0.5*N*(N+1):
        print(N)
        break
    N+=1

'''
count=0
x=[[0]]
for k in range(0,1000000):
    if X in x[k]:
        print(k)
        break
    x.append(list(set(x[k])))
    for j in range(len(x[k])):
        x[k+1].append(x[k][j]+k+1)
        x[k+1].append(x[k][j]-k-1)
    x[k+1]=list(set(x[k+1]))
'''
### BUGGY CODE ###

n = int(input())
nums = list(map(int, input().split()))
result = []

while(len(result) != n):
    result.append(str(nums.index(min(nums)) + 1))
    nums[nums.index(min(nums))] = 10**5 + 1

print((" ").join(result))

### FIXED CODE ###

n = int(input())
nums = list(map(int, input().split()))
pairlist = []
for i in range(len(nums)):
    pairlist.append([i, nums[i]])

sortedPairList = sorted(pairlist, key=lambda item: item[1])

result = []
for i in sortedPairList:
    result.append(str(i[0]+1))
print(" ".join(result))
### BUGGY CODE ###

s = input()
q = int(input())
query = [input() for i in range(q)]

for i in range(q):
  temp = query[i].split()
  if int(temp[0]) == 1:
    s = s[::-1]
  else:
    if int(temp[1]) == 1:
      s = temp[2] + s
    else:
      s = s + temp[2]

print(s)


### FIXED CODE ###

from collections import deque

def main():
  rev = False
  s = deque(input())
  q = int(input())
  query = tuple(input() for i in range(q))

  for i in range(q):
    temp = query[i].split()
    if int(temp[0]) == 1:
      rev = not rev
    else:
      if (int(temp[1]) == 1 and (not rev)) or (int(temp[1]) == 2 and rev):
        s.appendleft(temp[2])
      else:
        s.append(temp[2])

  if rev:
    s.reverse()

  print(''.join(s))

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

# -*- coding utf-8 -*-

a,b,x=map(int,input().split())
ans=0

for i in range(a,b+1):
    if i%x==0:
        ans+=1
    else:
        pass
print(ans)

### FIXED CODE ###

# -*- coding utf-8 -*-

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

print(b//x - (a-1)//x  )
### BUGGY CODE ###

from sys import stdin

import numpy as np

U = 10 ** 6 + 10


def main():
    readline = stdin.readline
    N = int(readline())
    a = list(map(int, readline().split()))
    mat = np.zeros(U + 1, np.int64)
    ret = 0
    for x in a:
        mat[x::x] += 1
    for x in a:
        ret += mat[x] == 1
    print(ret)

    
main()

### FIXED CODE ###

from sys import stdin

import numpy as np

U = 10 ** 6 + 10


def main():
    readline = stdin.readline
    N = int(readline())
    a = list(map(int, readline().split()))
    ret = 0
    exist_counts = [0] * U
    for x in a:
        if exist_counts[x]:
            exist_counts[x] = 2
            continue
        idx = x
        while idx < U:
            exist_counts[idx] += 1
            idx += x
    for x in a:
        ret += exist_counts[x] == 1
    print(ret)
main()
### BUGGY CODE ###

import math
MOD = 10**9 + 7 #　素数
x, y = map(int, input().split())

if (x+y)%3 != 0:
    print(0)
    exit()

if x == 0 or y == 0:
    print(0)
    exit()

X = max(x,y)
Y = min(x,y)

all_move = (X+Y)//3
diff = (X-Y)
Y_move = (all_move - diff)//2

def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

def inv_mod(a,mod):
    x = extgcd(a,mod)[0]
    return (mod+x%mod)%mod

def cmb_mod_p(n, r, mod): # nCr mod p
    if n<0 or r<0 or n<r:
        return 0

    res = 1
    for i in range(1,n+1):
        res = res*i%mod
    for i in range(1,r+1):
        res = res*inv_mod(i,mod)%mod
    for i in range(1,n-r+1):
        res = res*inv_mod(i,mod)%mod

    return res

print(cmb_mod_p(all_move, Y_move,MOD))



### FIXED CODE ###

import math
mod = 10**9 + 7
x, y = map(int, input().split())

if (x+y)%3 != 0:
    print(0)
    exit()

if x == 0 or y == 0:
    print(0)
    exit()

X = max(x,y)
Y = min(x,y)

all_move = (X+Y)//3
diff = (X-Y)
y_move = (all_move - diff)//2


def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

n = int(all_move)
r = int(y_move)
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

for i in range( 2, n + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )


print(cmb(n,r,mod))
### BUGGY CODE ###


def f():
  k = int(input())
  c = 0
  x = 0
  sx = 0
  while c < k:
    x+=1
    sx = str(x)
    c+=1
    for i in range(len(sx)-1):
      if abs(int(sx[i]) - int(sx[i+1])) > 1:
        c-=1
        break
  return x
import sys
sys.setrecursionlimit(100000)


print(f())

### FIXED CODE ###

kk = int(input())
if kk < 10:
    print(kk)
    exit()
 
 
dp = [[0] * 10 for _ in range(15)]
dp[0] = [1] * 10
for i in range(14):
    #dp[i+1][0] += sum(dp[i])
    for j in range(10):
        for k in range(-1, 2):
            if not (0 <= j + k < 10):
                continue
            dp[i + 1][j + k] += dp[i][j]
 
a = 0
for i in range(15):
    if a+sum(dp[i][1:]) >= kk:
        break
    a += sum(dp[i][1:])
 
ii = i
 
 
for j in range(1, 10):
    if a + dp[i][j] >= kk:
        kk -= a
        break
    a += dp[i][j]
 
ans = j
for i in reversed(range(ii)):
    a = 0
    for k in range(-1, 2):
        if not (0 <= j + k < 10):
            continue
        if a + dp[i][j + k] >= kk:
            kk -= a
            j = j + k
            ans = ans * 10 + j
 
            break
        a += dp[i][j + k]
 
 
print(ans)
### BUGGY CODE ###

N=int(input())
num=[int(input()) for i in range(N)]
num.sort()
jun=[]
sig=[i for i in range(1,N+1)]
if N%2!=0: #kisu
  manaka=int(N/2)
  if abs(num[manaka]-num[0])<abs(num[manaka]-num[N-1]):
    jun.append(manaka)
    for i in range(int((N-1)/2)):
      jun.append(max(sig)-1)
      sig.remove(max(sig))
      jun.append(min(sig)-1)
      sig.remove(min(sig))
  else:
    jun.append(manaka)
    for i in range(int((N-1)/2)):
      jun.append(min(sig)-1)
      sig.remove(min(sig))
      jun.append(max(sig)-1)
      sig.remove(max(sig))
else:
  manaka=int(N/2)
  jun.append(manaka)
  for i in range(manaka-1):
    jun.append(min(sig)-1)
    sig.remove(min(sig))
    jun.append(max(sig)-1)
    sig.remove(max(sig))
  jun.append(sig[0]-1)
delta=[abs(num[jun[i]]-num[jun[i+1]]) for i in range(N-1)]
print(sum(delta))

### FIXED CODE ###

N=int(input())
num=[int(input()) for i in range(N)]
num.sort()

if N%2!=0: #kisu
  manaka=int(N/2)  
  sum_a=abs(num[manaka]-num[N-1])
  sum_a+=abs(num[N-1]-num[0])
  for i in range(int((N-1)/2)-1):
    sum_a+=abs(num[N-2-i]-num[i])
    sum_a+=abs(num[i+1]-num[N-2-i])
  sum_b=abs(num[manaka]-num[0])
  sum_b+=abs(num[0]-num[N-1])
  for i in range(int((N-1)/2)-1):
    sum_b+=abs(num[i+1]-num[N-1-i])
    sum_b+=abs(num[i+1]-num[N-2-i])
  print(max(sum_a,sum_b))
else:
  manaka=int(N/2)
  sum=abs(num[manaka]-num[0])
  for i in range(manaka-1):
    sum+=abs(num[i]-num[N-1-i])
    sum+=abs(num[i+1]-num[N-1-i])
  print(sum)