Harryxun/stf_run huggingface dataset:
class UnionFind:
    def __init__(self, size: int):
        self.parent = [-1 for _ in range(size)]
        self.size = [1 for _ in range(size)]

    def unite(self, x, y):
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return
        if self.parent[px] > self.parent[py]:
            px, py = py, px
        self.parent[px] = py
        self.parent[py] -= 1
        self.size[py] += self.size[px]
        self.size[px] = 0

    def find(self, x: int) -> int:
        if self.parent[x] < 0:
            return x
        self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def is_same(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)


def main():
    # input
    N, M = map(int, input().split())
    A = list()
    B = list()

    for i in range(M):
        pair = list(map(int, input().split()))
        A.append(pair[0])
        B.append(pair[1])

    # solve
    # ref: http://drken1215.hatenablog.com/entry/2019/03/03/224600
    # ref: https://atcoder.jp/contests/abc120/submissions/4450601
    uf = UnionFind(N)
    ans = [N*(N-1)//2]
    for i in range(M-1, 0, -1):
        p1 = uf.find(A[i])
        p2 = uf.find(B[i])
        if p1 != p2:
            ans.append(ans[-1] - uf.size[p1]*uf.size[p2])
        else:
            ans.append(ans[-1])
        uf.unite(p1, p2)
    return ans


print(*list(reversed(main())), sep="\n")


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)


class UnionFind:
    def __init__(self, size: int):
        self.parent = [-1 for _ in range(size)]
        self.size = [1 for _ in range(size)]

    def unite(self, x, y):
        px = self.find(x)
        py = self.find(y)
        if px != py:
            if self.parent[px] > self.parent[py]:
                self.parent[py] = px
                self.parent[px] -= 1
                self.size[px] += self.size[py]
                self.size[py] = 0
            else:
                self.parent[px] = py
                self.parent[py] -= 1
                self.size[py] += self.size[px]
                self.size[px] = 0
        return

    def find(self, x: int) -> int:
        if self.parent[x] < 0:
            return x
        self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def is_same(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)


def main():
    # input
    N, M = map(int, input().split())
    brs = [list(map(int, input().split())) for _ in range(M)]

    # solve
    # ref: http://drken1215.hatenablog.com/entry/2019/03/03/224600
    # ref: https://atcoder.jp/contests/abc120/submissions/4450601
    uf = UnionFind(N)
    ans = [N*(N-1)//2]
    for i in range(M-1, 0, -1):
        a, b = brs[i][0], brs[i][1]
        a, b = a-1, b-1
        p1 = uf.find(a)
        p2 = uf.find(b)
        if p1 != p2:
            ans.append(ans[-1] - uf.size[p1]*uf.size[p2])
        else:
            ans.append(ans[-1])
        uf.unite(p1, p2)
    return ans


print(*list(reversed(main())), sep="\n")
import sys
from heapq import *
input = sys.stdin.readline

def main():
    n, q = map(int, input().split())
    
    key = []
    for i in range(n):
        s, t, x = map(int, input().split())
        l, r = max(0, s-x), max(0, t-x)
        key.append((l, 1, x))
        key.append((r, -1, x))

    key.sort()
    judge = []
    now = set()
    already = dict()
    
    index = 0
    ans = -1
    for i in range(q):
        d = int(input())
        for i in range(index, 2*n):
            s, j, x = key[i]
            if s > d:
                index = i
                break
            if j == 1:
                heappush(judge, x)
                now = now.add(x)
            else:
                now.discard(x)
                if x in already:
                    already[x] += 1
                else:
                    already[x] = 1
                    
                    
        while judge:
            if judge[0] in already and already[judge[0]] > 0:
                already[judge[0]] -= 1
                heappop(judge)
            else:
                break
        if judge:
            ans = judge[0]
        else:
            ans = -1      
            
        print(ans)

    
if __name__ == "__main__":
    main()



### FIXED CODE ###

import sys
from heapq import *
input = sys.stdin.readline

def main():
    n, q = map(int, input().split())
    
    key = []
    for i in range(n):
        s, t, x = map(int, input().split())
        l, r = max(0, s-x), max(0, t-x)
        key.append((l, 1, x))
        key.append((r, -1, x))
    
    for i in range(q):
        d = int(input())
        key.append((d, 2))

    key.sort()
    judge = []
    already = dict()
    
    for i in range(2*n+q):
        k = key[i]
        if k[1] == -1:
            if k[2] in already:
                already[k[2]] += 1
            else:
                already[k[2]] = 1
        elif k[1] == 1:
            heappush(judge, k[2])
        else:
            while judge:
                if judge[0] in already and already[judge[0]] > 0:
                    already[judge[0]] -= 1
                    heappop(judge)
                else:
                    break
            if judge:
                print(judge[0])
            else:
                print(-1)
    

    
if __name__ == "__main__":
    main()
a,b=map(int,input.split())
print(a-b+1)

### FIXED CODE ###

a,b=map(int,input().split())
print(a-b+1)
c=[list(map(int,input().split())) for i in range(3)]



for i in range(101):
　info=True
　a1=i
  b1=c[0][0]-a1
  b2=c[0][1]-a1
  b3=c[0][2]-a1
  a2=c[1][0]-b1
  a3=c[2][0]-b1
  if min(a1,a2,a3,b1,b2,b3)<0:
    info=False
  if c[1][1]!=a2+b2:
    info=False
  if c[2][1]!=a3+b2:
    info=False
  if info:
    print("Yes")
    break
else:
  print("No")

### FIXED CODE ###

c=[list(map(int,input().split())) for i in range(3)]


  
for i in range(101):
  info=True
  a1=i
  b1=c[0][0]-a1
  b2=c[0][1]-a1
  b3=c[0][2]-a1
  a2=c[1][0]-b1
  a3=c[2][0]-b1
  if min(a1,a2,a3,b1,b2,b3)<0:
    info=False
  if c[1][1]!=a2+b2:
    info=False
  if c[2][1]!=a3+b2:
    info=False
  if c[1][2]!=a2+b3:
    info=False
  if c[2][2]!=a3+b3:
    info=False
  
  if info:
    print("Yes")
    break
else:
  print("No")
from collections import deque
import sys

stdin = sys.stdin
def li(): return map(int, stdin.readline().split())

N, M = tuple(li())
stack = []
for i in range(M):
    stack.append( tuple(li()) )

p_map = {}
for i in range(1, N + 1):
    # key: val
    # node_id: parent_id, union_size
    p_map[i] = [i, 1]

combs = deque()
def parent(i):
    if p_map[i][0] == i:
        return i
    else:
        return parent(p_map[i][0])
while stack:
    l, r = stack.pop()
    # parent should be greater
    if parent(l) < parent(r):
        l, r = r, l
    if parent(l) == parent(r):
        if combs:
            combs.appendleft(combs[0])
    else:
        p_map[r][0] = l
        incr = p_map[parent(l)][1] * p_map[parent(r)][1]
        p_map[l][1] += p_map[r][1]
        if combs:
            combs.appendleft(combs[0] + incr)
        else:
            combs.appendleft(incr)

cnt = 0
cur = combs[0]
combs.append(0)
while combs:

    cur = combs.popleft()
    cnt += cur - combs[0]
    print(cnt)


### FIXED CODE ###

from collections import deque
import sys

stdin = sys.stdin
def li(): return map(int, stdin.readline().split())

N, M = tuple(li())
stack = []
for i in range(M):
    stack.append( tuple(li()) )

p_map = {}
for i in range(1, N + 1):
    # key: val
    # node_id: parent_id, union_size
    p_map[i] = [i, 1]

combs = deque()
def parent(i):
    if p_map[i][0] == i:
        return i
    else:
        return parent(p_map[i][0])
while stack:

    l, r = stack.pop()
    p_l = parent(l)
    p_r = parent(r)
    # parent should be greater
    if p_l == p_r:
        if combs:
            combs.appendleft(combs[0])
    else:
        if p_l < p_r:
            p_l, p_r = p_r, p_l
        p_map[p_r][0] = p_l
        incr = p_map[p_l][1] * p_map[p_r][1]
        p_map[p_l][1] += p_map[p_r][1]
        if combs:
            combs.appendleft(combs[0] + incr)
        else:
            combs.appendleft(incr)
cnt = 0
combs.append(0)
while combs:
    cur = combs.popleft()
    if combs:
        cnt += cur - combs[0]
        print(cnt)
import sys
from collections import deque
import copy

def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def power_func(a,b,p):
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, A, B, K] = [long(input_raw[0]), long(input_raw[1]), long(input_raw[2]), long(input_raw[3])]
    cnt = 0
    li = []
    for t in range(N + 1):
        if (K - t * A)%B == 0:
            u = (K - t * A)/B
            if t >= 0 and u >= 0 and t <= N and u <= N:
                li.append((t, u))


    frac_N = [0 for i in range(N + 1)]
    power_N = [0 for i in range(N + 1)]
    frac_N[0] = 1
    power_N[0] = 1
    p = 998244353L
    for i in range(1, N + 1):
        frac_N[i] = (frac_N[i - 1] * i ) % p
        power_N[i] = -1

    s = 0L
    for i in range(len(li)):
        t = li[i][0]
        u = li[i][1]
        if power_N[t] == -1:
            power_N[t] = power_func(frac_N[t], p - 2, p)
        if power_N[N - t] == -1:
            power_N[N - t] = power_func(frac_N[N - t], p - 2, p)
        if power_N[u] == -1:
            power_N[u] = power_func(frac_N[u], p - 2, p)
        if power_N[N - u] == -1:
            power_N[N - u] = power_func(frac_N[N - u], p - 2, p)

        s = (s + ((frac_N[N] * power_N[t] * power_N[N - t]) % p) * ((frac_N[N] * power_N[u] * power_N[N - u]) % p)) % p
    print s


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from collections import deque
import copy

from math import *

def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    N = int(input_raw[0])
    min_s = sys.maxint
    for i in range(1, N):
        A = str(i)
        A = A.zfill(6)
        B = str(N - i)
        B = B.zfill(6)
        s = 0
        for j in range(6):
            s += int(A[j]) + int(B[j])
        min_s = min(s, min_s)

    print min_s
if __name__ == '__main__':
    main()
n, m = map(int, input().split())
room_adjacent = [[] for _ in range(n)]
for _ in range(m):
  room1, room2 = map(int, input().split())
  room_adjacent[room1-1].append(room2)
  room_adjacent[room2-1].append(room1)

def label_rooms(old_room):
  for room in room_adjacent[old_room-1]:
    if room_labels[room-1] == 0: room_labels[room-1] = old_room
  for room in room_adjacent[old_room-1]:
    if room_labels[room-1] == old_room: label_rooms(room)

room_labels = [1]+[0]*(n-1)
label_rooms(1)
if 0 in room_labels:
  print("No")
else:
  print("Yes")
  [print(value) for value in room_labels[1:]]

### FIXED CODE ###

from collections import deque
n, m = map(int, input().split())
room_adjacent = [[] for _ in range(n)]
for _ in range(m):
  room1, room2 = map(int, input().split())
  room_adjacent[room1-1].append(room2)
  room_adjacent[room2-1].append(room1)

room_labels = [1]+[0]*(n-1)
old_room = 1
path_queue = deque((old_room, room) for room in room_adjacent[old_room-1])
while path_queue:
  old_room, new_room = path_queue.pop()
  if room_labels[new_room-1] == 0:
    room_labels[new_room-1] = old_room
    for another_room in room_adjacent[new_room-1]:
      path_queue.appendleft((new_room, another_room))
  
if 0 in room_labels:
  print("No")
else:
  print("Yes")
  [print(value) for value in room_labels[1:]]
num = (10 ** 9) + 7

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

prime_upper = int(m ** (1/2) + 50)
prime_dict = {}

check = [False] * prime_upper
prime = [2]

while m % 2 == 0:
    m //= 2
    if not 2 in prime_dict.keys():
        prime_dict[2] = 0
    prime_dict[2] += 1

for j in range(2, prime_upper, 2):
    check[j] = True

for i in range(3, prime_upper, 2):
    if not check[i]:
        prime.append(i)
        while m % i == 0:
            m //= i
            if not i in prime_dict.keys():
                prime_dict[i] = 0
            prime_dict[i] += 1

        for j in range(i, prime_upper, i):
            check[j] = True

value_max = max(prime_dict.values())
com2 = [[0] * (value_max + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    for j in range(1, value_max + 1):
        if i == 1:
            com2[i][j] = 1
        elif j == 1:
            com2[i][j] = i
        else:
            com2[i][j] = (com2[i][j - 1] + com2[i - 1][j]) % num
if m != 1:
    ans = n
else:
    ans = 1
for key, value in prime_dict.items():
    ans = (ans * com2[n][value]) % num

print(ans)

### FIXED CODE ###

num = (10 ** 9) + 7

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

if m == 1:
    print(1)
    exit()

prime_upper = int(m ** (1/2) + 50)
prime_dict = {}

check = [False] * prime_upper
prime = [2]

while m % 2 == 0:
    m //= 2
    if not 2 in prime_dict.keys():
        prime_dict[2] = 0
    prime_dict[2] += 1

for j in range(2, prime_upper, 2):
    check[j] = True

for i in range(3, prime_upper, 2):
    if not check[i]:
        prime.append(i)
        while m % i == 0:
            m //= i
            if not i in prime_dict.keys():
                prime_dict[i] = 0
            prime_dict[i] += 1

        for j in range(i, prime_upper, i):
            check[j] = True

if len(prime_dict.values()) != 0:
    value_max = max(prime_dict.values())
    com2 = [[0] * (value_max + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, value_max + 1):
            if i == 1:
                com2[i][j] = 1
            elif j == 1:
                com2[i][j] = i
            else:
                com2[i][j] = (com2[i][j - 1] + com2[i - 1][j]) % num
    if m != 1:
        ans = n
    else:
        ans = 1
    for key, value in prime_dict.items():
        ans = (ans * com2[n][value]) % num
    print(ans)
else:
    print(n)
C = X[2]
D = X[3]


n = 0
while C>0:
  C = C-B
  n += 1

m = 0
while A>0:
  A -= D
  m += 1
print(n,m)
if n<=m:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

X = list(map(int,input().split()))

A = X[0]
B = X[1]
C = X[2]
D = X[3]


n = 0
while C>0:
  C = C-B
  n += 1

m = 0
while A>0:
  A = A-D
  m += 1

if n<=m:
  print("Yes")
else:
  print("No")
S=input()
T=input()
flag = True
for i in range(N):
    s = S[i]
    t = T[i]
    if s != t:
        flag = False
        
if flag:
    if len(T) == N+1:
        print("Yes")
    else:
        print("No")
else:
    print("No")

### FIXED CODE ###

s = input()
t = input()
if s == t[:-1]:
  print('Yes')
else:
  print('No')
A,B,K=map(int,input().split())

if A-K=>0:
  print(A-K,B)
elif (A+B)<=K:
  print(0,0)
else:
  print(0,A+B-K)

### FIXED CODE ###

A,B,K=map(int,input().split())
 
if A-K>=0:
  print(A-K,B)
elif (A+B)<=K:
  print(0,0)
else:
  print(0,A+B-K)
n, m = map(int, input().split())

stairs = []
is_continuous = False
for i in range(m):
    stairs.append(int(input()))
    if i > 0 and stairs[i] - 1 == stairs[i - 1]:
        is_continuous = True
        break

if is_continuous:
    print(0)
else:
    countup_num = [0] * (n + 1)
    countup_num[0] = 1
    countup_num[1] = 1
    for i in range(2, n + 1):
        countup_num[i] = (countup_num[i - 1] + countup_num[i - 2]) % 1000000007
    res = 1
    diff = 0
    now = 0
    for i in range(m):
        diff = stairs[i] - now - 1
        now = stairs[i] + 1
        res *= (countup_num[diff]) % 1000000007
        # print(res, now)
    diff = n - stairs[-1] - 1
    res *= (countup_num[diff]) % 1000000007

    res %= 1000000007
    # print(countup_num)
    print(res)


### FIXED CODE ###

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

stairs = []
is_continuous = False
for i in range(m):
    stairs.append(int(input()))
    if i > 0 and stairs[i] - 1 == stairs[i - 1]:
        is_continuous = True
        break

if is_continuous:
    print(0)
else:
    countup_num = [0] * (n + 1)
    countup_num[0] = 1
    countup_num[1] = 1
    for i in range(2, n + 1):
        countup_num[i] = (countup_num[i - 1] + countup_num[i - 2]) % 1000000007
    res = 1
    diff = 0
    now = 0
    for i in range(m):
        diff = stairs[i] - now - 1
        now = stairs[i] + 1
        res *= (countup_num[diff]) % 1000000007
        # print(res, now)
    if m == 0:
        res = countup_num[n]
    else:
        diff = n - stairs[-1] - 1
        res *= (countup_num[diff]) % 1000000007

    res %= 1000000007
    # print(countup_num)
    print(res)
n,m=map(int,input().split())
a=sorted([int(i) for i in input().split()])
import bisect

def hantei(now):
    num=0
    for ax in a:
        bi = bisect.bisect_left(a,now-ax)
        num+= bi
#         print(now,ax,bi)
    return n**2-num

mi = a[0]*2-1
ma = a[-1]*2+1
while mi<ma:
    now=(mi+ma)//2
    which = hantei(now)<=m#なんか判定
    if which:
        ma=now
        kotae=now
    else:
        mi=now+1
kotae-=1

suma=[0]*(n+1)
suma[-2]=a[-1]
for i in range(n-2,-1,-1):
    suma[i] = suma[i+1]+a[i]
    
ans=0
kazu=0
for ax in a:
    bi = bisect.bisect_left(a,kotae-ax)
    ans+= (n-bi)*ax+suma[bi]
    kazu+=n-bi
print(ans-(kazu-m)*kotae)

### FIXED CODE ###

n,m=map(int,input().split())
a=sorted([int(i) for i in input().split()])
import bisect

def hantei(now):
    num=0
    for ax in a:
        bi = bisect.bisect_left(a,now-ax)
        num+= bi
#         print(now,ax,bi)
    return n**2-num

mi = a[0]*2-1
ma = a[-1]*2+1
kotae=ma
while mi<ma:
    now=(mi+ma)//2
    which = hantei(now)<=m#なんか判定
    if which:
        ma=now
        kotae=now
    else:
        mi=now+1
kotae-=1

suma=[0]*(n+1)
suma[-2]=a[-1]
for i in range(n-2,-1,-1):
    suma[i] = suma[i+1]+a[i]
    
ans=0
kazu=0
for ax in a:
    bi = bisect.bisect_left(a,kotae-ax)
    ans+= (n-bi)*ax+suma[bi]
    kazu+=n-bi
print(ans-(kazu-m)*kotae)
import itertools
import numpy as np
n,m = map(int,input().split())
M = [[0] * n for i in range(m)]

for i in range(m):
  a,b = map(int,input().split())
  M[a-1][b-1] = 1
couse = list(itertools.permutations(range(n)))
result = 0
M = np.array(M)
for c in couse:
  con = 0
  if(c[0] == 0):
    for i in range(len(c)-1):
      if(M[c[i]][c[i+1]] == 1 or M[c[i+1]][c[i]] == 1):
        con += 1
        #print(c[i],c[i+1])
    if (len(c)-1 == con):
      result += 1
print(result)

### FIXED CODE ###

import itertools
n,m = map(int,input().split())
M = [[0] * n for i in range(n)]

for i in range(m):
  a,b = map(int,input().split())
  M[a-1][b-1] = 1
couse = list(itertools.permutations(range(n)))
result = 0
#M = np.array(M)
for c in couse:
  con = 0
  if(c[0] == 0):
    for i in range(len(c)-1):
      if(M[c[i]][c[i+1]] == 1 or M[c[i+1]][c[i]] == 1):
        con += 1
        #print(c[i],c[i+1])
    if (len(c)-1 == con):
      result += 1
print(result)
x = inpput()
print(x//500 * 1000 + x%500//5 * 5)

### FIXED CODE ###

x = int(input())
print(x//500 * 1000 + x%500//5 * 5)
data = [[[0 for r in range(10)] for f in range(3)] for b in range(4)]

n = int(input())

for _ in range(n):
    (b,f,r,v) = [int(i) for i in input().split()]
    data[b - 1][f - 1][r - 1] += v

for b in range(4):
    for f in range(3):
        for r in range(10):
            print('',data[b][f][r], end='')
        print()
    if b < 3:
        print('#' * 20)

### FIXED CODE ###


data = [[[0 for r in range(10)] for f in range(3)] for b in range(4)]

n = int(input())

for _ in range(n):
    (b,f,r,v) = [int(i) for i in input().split()]
    data[b - 1][f - 1][r - 1] += v

for b in range(4):
    for f in range(3):
        for r in range(10):
            print('',data[b][f][r], end='')
        print()
    if b < 3:
        print('#' * 20)
import math
S = input()
Q = int(input())

lr = 'left'

def reverse_list(lr):
    if lr == 'right':
        return 'left'
    else:
        return 'right'

def moji_tuika(S, f, c, lr):
    if f == 1 and lr == 'left':
        return S.insert(0,c)
    elif f == 1 and lr == 'right':
        return S.append(c)
    elif f == 2 and lr == 'left':
        return S.append(c)
    else:
        return S.insert(0,c)
q = []
for i in range(Q):
    temp = input().split()
    if len(temp) == 1:
        q.append(1)
    else:
        q.append(temp)

S = list(S)
for i in q:
    if type(i) == int:
        lr = reverse_list(lr)
    elif int(i[0]) == 2:
        S = moji_tuika(S,int(i[1]),i[2],lr)

if lr == 'right':
    S.reverse()

S = ''.join(S)
print(S)


### FIXED CODE ###

from collections import deque

S = input()
Q = int(input())

lr = 'left'

def reverse_list(lr):
    if lr == 'right':
        return 'left'
    else:
        return 'right'

def moji_tuika(S, f, c, lr):
    if f == 1 and lr == 'left':
        S.appendleft(c)
    elif f == 1 and lr == 'right':
        S.append(c)
    elif f == 2 and lr == 'left':
        S.append(c)
    else:
        S.appendleft(c)
    return S

q = []
for i in range(Q):
    temp = input().split()
    if len(temp) == 1:
        q.append(1)
    else:
        q.append(temp)

S = deque(list(S))
for i in q:

    if type(i) == int:
        lr = reverse_list(lr)
    elif int(i[0]) == 2:
        S = moji_tuika(S,int(i[1]),i[2],lr)
if lr == 'right':
    S.reverse()

S = ''.join(S)
print(S)
N = int(input())
A = list(map(int,input().split()))
checklist = list(set(A))
dic = {}
nCrdic = {}
nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]

for i in checklist:
    dic[i] = A.count(i)
for key,value in dic.items():
    nCrdic[key] = cmb(value,2) if value > 1 else 0
for i in A:
    if dic[i] > 2:
        ans = sum(nCrdic.values()) - nCrdic[i] + cmb(dic[i]-1,2)
    else: ans = sum(nCrdic.values()) - nCrdic[i]
    print(ans)

### FIXED CODE ###

from collections import Counter

N = int(input())
A = list(map(int,input().split()))
countdic = Counter(A)
goukei = 0
ans = ''
for key,value in countdic.items():
    goukei += (value*(value-1))//2
for i in A:
    ans = goukei -(countdic[i]*(countdic[i]-1))//2 + ((countdic[i]-1)*(countdic[i]-2))//2
    print(ans)
n = int(input())

arr = []
for i in range(10000):
    si = str(i + 1)
    for i2 in range(len(si) - 1):
        if abs(int(si[i2]) - int(si[i2 + 1])) >= 2:
            break
    else:
        arr.append(si)

print(arr[n - 1])


### FIXED CODE ###

import math

k = int(input())

l = [1, 2, 3, 4, 5, 6, 7, 8, 9]

c = 0
while k > len(l):
    f = l[c] - (l[c] // 10 * 10)

    if f != 0:
        l.append(l[c] * 10 + f - 1)

    l.append(l[c] * 10 + f)

    if f != 9:
        l.append(l[c] * 10 + f + 1)

    c += 1

print(l[k - 1])
import pandas as pd

H,W,K = list(map(int, input().split()))
t=[]
for i in range(H):
    t.append([int(i) for i in input().replace(".","0").replace("#","1")])

cnt = 0
for i in range(2**H):
    for j in range(2**W):
        d = pd.DataFrame(t)
        i_2 = [int(k) for k in bin(i)[2:].rjust(H,"0")]
        j_2 = [ int(k) for k in bin(j)[2:].rjust(W,"0")]
        #print(i_2)
        #print(j_2)
        
        for h in range(H):
            d.iloc[h,:] = d.iloc[h,:] * i_2[h]
        for w in range(W):
            d.iloc[:,w] = d.iloc[:,w] * j_2[w]
        num = sum((d == 1).sum())
        #print(num)
        #print(d)
        if num == K:
            cnt +=1
            
print(cnt)

### FIXED CODE ###

import numpy as np

H,W,K = list(map(int, input().split()))
t=[]
for i in range(H):
    t.append([int(i) for i in input().replace(".","0").replace("#","1")])

cnt = 0
for i in range(2**H):
    for j in range(2**W):
        d = np.array(t)
        i_2 = [int(k) for k in bin(i)[2:].rjust(H,"0")]
        j_2 = [ int(k) for k in bin(j)[2:].rjust(W,"0")]
        #print(i_2)
        #print(j_2)
        
        d= ((d.T)*i_2).T
        d= d*j_2
        
        num = d.sum()
        if num == K:
            cnt +=1
            
print(cnt)