Harryxun/stf_run huggingface dataset:
while True:
    n = int(raw_input())
    if n == 0:
        break
    m = int(raw_input())-1
    x = int(raw_input())-1
    d = int(raw_input())
    amida = []
    for i in range(d):
        amida.append(map(int, raw_input()))
    rroot = []
    for i in range(d-1,-1,-1):
        if x > 0:
            if amida[i][x-1] == 1:
                x -= 1
        if x < 4:
            if amida[i][x] == 1:
                x += 1
        rroot.append(x)
    if m == x:
        print 0
    else:
        root = []
        for i in range(d):
            if m > 0:
                if amida[i][m-1] == 1:
                    m -= 1
            if m < 4:
                if amida[i][m] == 1:
                    m += 1
            root.append(m)
        rroot.reverse()
        for i in range(d):
            k = root[i] - rroot[i]
            if abs(k) == 1:
                p = min(root[i],rroot[i])
                if sum(amida[i][p-1:p+1]) == 0:
                    print i+1, p+1
                    break
            if i == d-1:
                print 1

### FIXED CODE ###

while True:
    n = int(raw_input())
    if n == 0:
        break
    m,x,d = int(raw_input()),int(raw_input()),int(raw_input())
    amida = ["" for i in range(d)]
    for i in range(d):
        amida[i] = "0" + raw_input() + "0"
    rroot = []
    for i in range(d-1,-1,-1):
        if amida[i][x-1] == "1": x -= 1
        elif amida[i][x] == "1" : x += 1
        rroot.append(x)

    if m == x: print 0
    else:
        root = []
        for i in range(d):
            if amida[i][m-1] == "1": m -= 1
            elif amida[i][m] == "1" : m += 1
            root.append(m)
        rroot.reverse()
        for i in range(d):
            if abs(root[i]-rroot[i]) == 1:
                p = min(root[i],rroot[i])
                if int(amida[i][p-1]) + int(amida[i][p+1]) == 0:
                    print i+1, p
                    break
            if i == d-1: print 1
from collections import deque
a=int(input())
q=deque([1,2,3,4,5,6,7,8,9])
def dfs(k):
  while k=a:
    s=q.popleft()
    if s-1>=0:
      q.aapend(s*10+s-1)
      n=n+1
    q.append(s*10+s)
    k=k+1
    if s+1<=9:
      q.append(s*10+s+1)
      k=k+1
  print(q.pop())
 
if a<=9:
  print(a)
else:
  dfs(9)

### FIXED CODE ###

from collections import deque
a=int(input())
q=deque([1,2,3,4,5,6,7,8,9])
def dfs(k):
  while k<=a:
    s=q.popleft()
    if s%10-1>=0:
      q.append(s*10+s%10-1)
      k=k+1
      if k==a:
        print(q.pop())
    q.append(s*10+s%10)
    k=k+1
    if k==a:
        print(q.pop())
    if s%10+1<=9:
      q.append(s*10+s%10+1)
      k=k+1
      if k==a:
        print(q.pop())
  
 
if a<=9:
  print(a)
else:
  dfs(9)
print(hello)

### FIXED CODE ###

x = input().split()
sum1 = int(x[0]) + int(x[1])
sum2 = int(x[1]) + int(x[2])
sum3 = int(x[0]) + int(x[2])
print(min(sum1, sum2, sum3))
l,r=map(int,input().split())
k=min(l%2019,(r+1)%2019)
m=max(l%2019,(r+1)%2019)
a=list(range(k,m))
a.sort()
print(min(i*j % 2019 for i in a for j in a if i<j))

### FIXED CODE ###

l,r=map(int,input().split())
a=range(l,r+1)[:673]
print(min(i*j % 2019 for i in a for j in a if i<j))
n,h = (int(i) for i in input().split())
x = [[int(i) for i in input().split()] for i in range(n)]
a,b = 0,[]
for j in x:
	if a < j[0]: a = j[0]
	b.append(j[1])
num = 0
for j2 in b:
	if j2 >= a and h>0:
		h -= j2
		num +=1
if h<=0: print(num)
else:
	if h%a==0: answer = (h-h%a)//a + num
	else: answer = (h-h%a)//a + num + 1
    print(answer)

### FIXED CODE ###

def main():
    N, H = map(int, input().split())
    AB = (tuple(map(int, input().split())) for _ in [0] * N)
    a, b = [], []
    appenda, appendb = a.append, b.append
    for i, j in AB:
        appenda(i)
        appendb(j)

    amax = max(a)
    b = [i for i in b if i > amax]
    b.sort(reverse=1)
    energy = H
    if energy <= sum(b):
        attack = 0
        i = 0
        while energy > 0:
            energy -= b[i]
            attack += 1
            i += 1
    else:
        energy -= sum(b)
        attack = (energy + amax - 1) // amax + len(b)

    print(attack)

main()
# coding: utf-8

"""

o 999
o 2 3
x 2 0 2
o 2 1 2
x 2 1 2 1
o 2 1 3 1
o 2 1 3 2
o 3 1 3
x 3 2 3
o 3 2 2

- 0は両端のみ
- 偶奇の切り替わりが2回以下

zzoo
zzee
zzooee
zzeeoo
zzooeeoo xxx
zzeeooee
zz
???zz
"""

ooeeooee
L = input()
A = [input() for _ in range(L)]

T = [L,L,L,L,L,L,0,L]
for a in A:
  P = T
  o = 1-a%2
  e = 1-o
  if a==0:
    e = 2
  T = [
    min(P[0]+o, P[6]+o),
    min(P[1]+e, P[6]+e),
    min(P[2]+e, P[0]+e),
    min(P[3]+o, P[1]+o),
    min(P[4]+o, P[2]+o),
    min(P[5]+e, P[3]+e),
    P[6]+a,
    min(P)+a,
  ]
  #print a, T
print min(T[4:]+T[5:])



### FIXED CODE ###

# coding: utf-8

"""

o 999
o 2 3
x 2 0 2
o 2 1 2
x 2 1 2 1
o 2 1 3 1
o 2 1 3 2
o 3 1 3
x 3 2 3
o 3 2 2

- 0は両端のみ
- 偶奇の切り替わりが2回以下

0 zzoo
1 zzee
2 zzooee
3 zzeeoo
4 zzeeooee
5 zz
6 ???zz
"""

L = input()
A = [input() for _ in range(L)]

T = [L,L,L,L,L,0,L]
for a in A:
  P = T
  o = 1-a%2
  e = 1-o
  if a==0:
    e = 2
  T = [
    min(P[0]+o, P[5]+o),
    min(P[1]+e, P[5]+e),
    min(P[2]+e, P[0]+e),
    min(P[3]+o, P[1]+o),
    min(P[4]+e, P[3]+e),
    P[5]+a,
    min(P)+a,
  ]
  #print a, T
print min(T)
import itertools, operator


def out(X):
    print(list(itertools.accumulate(X, func=lambda x, y: x * y % mod))[-1])
    exit()


N, K = [int(_) for _ in input().split()]
A = sorted([int(_) for _ in input().split()], key=lambda x: -abs(x))
mod = 10**9 + 7
cnt = 0
ipos = ineg = -1
for i, a in enumerate(A[:K]):
    if a < 0:
        cnt += 1
        ineg = i
    else:
        ipos = i
if cnt % 2 == 0:
    out(A[:K])
else:
    for i, a in enumerate(A[K:]):
        if a < 0 and ipos != -1:
            X = A[:ipos] + A[ipos + 1:K] + A[K + i]
            out(X)
        elif a > 0 and ineg != -1:
            X = A[:ineg] + A[ineg + 1:K] + A[K + i]
            out(X)
    else:
        C = A[::-1]
        cnt = 0
        out(C[:K])


### FIXED CODE ###

import itertools


def out(X):
    return list(itertools.accumulate(X, func=lambda x, y: x * y % mod))[-1]


N, K = [int(_) for _ in input().split()]
A = sorted([int(_) for _ in input().split()], key=lambda x: -abs(x))
mod = 10**9 + 7
cnt = 0
ipos = ineg = -1
for i, a in enumerate(A[:K]):
    if a < 0:
        cnt += 1
        ineg = i
    else:
        ipos = i
if cnt % 2 == 0:
    print(out(A[:K]))
else:
    oneg = opos = -10**10
    for i, a in enumerate(A[K:]):
        if a < 0 and ipos != -1:
            X = A[:ipos] + A[ipos + 1:K] + [A[K + i]]
            oneg = out(X)
            beforeneg = A[ipos]
            afterneg = A[K + i]
            ipos = -1
        elif a > 0 and ineg != -1:
            Y = A[:ineg] + A[ineg + 1:K] + [A[K + i]]
            opos = out(Y)
            beforepos = A[ineg]
            afterpos = A[K + i]
            ineg = -1
    if oneg != -10**10 and opos != -10**10:
        #afterneg/beforeneg > afterpos>beforepos
        if afterneg * beforepos > afterpos * beforeneg:
            print(oneg)
        else:
            print(opos)
    elif oneg != -10**10 or opos != -10**10:
        print(max(opos, oneg))
    else:
        C = A[::-1]
        print(out(C[:K]))
length = int(input())
text = input()

r_count = text.count("R")
g_count = text.count("G")
b_count = text.count("B")

answer = r_count * g_count * b_count

for i in range(length-2):
    for j in range(i+1, length-1):
        k = i + (i-j)*2
        if k < length and text[i]!=text[j] and text[i]!=text[k] and text[j]!=text[k]:
            answer -= 1
        
print(answer)

### FIXED CODE ###

length = int(input())
text = input()

r_count = text.count("R")
g_count = text.count("G")
b_count = text.count("B")

answer = r_count * g_count * b_count

for i in range(length-2):
    for j in range(i+1, length-1):
        k = i + (j-i)*2
        if k < length and text[i]!=text[j] and text[i]!=text[k] and text[j]!=text[k]:
            answer -= 1
        
print(answer)
input()

ans = 0
a = [int(i) for i in input().split()]

for num in a:
  ans += num - 1
  
 print(ans)

### FIXED CODE ###

a  = input()
 
ans = 0
a = [int(i) for i in input().split()]
 
for num in a:
  ans += num - 1
  
print(ans)
from collections import deque

N, M, K = [int(n) for n in input().split()]
desk_a = deque([int(n) for n in input().split()], maxlen=200001)
desk_b = deque([int(n) for n in input().split()], maxlen=200001)

def max_n_book(desk_a, desk_b, count=0, k=K):
    if k < 0:
        return count - 1
    if len(desk_a) != 0:
        # book_a = desk_a.popleft()
        # count_a = max_n_book(desk_a, desk_b, count=count+1, k=k-book_a)
        count_a = 0
    else:
        count_a = count
    if len(desk_b) != 0:
        # book_b = desk_b.popleft()
        # count_b = max_n_book(desk_b, desk_b, count=count+1, k=k-book_b)
        count_a = 0
    else:
        count_b = count
    return max(count_a, count_b)

n_book = max_n_book(desk_a, desk_b, count=0, k=K)
print(n_book)


### FIXED CODE ###

N, M, K = map(int, input().split())
desk_a = list(map(int, input().split()))
desk_b = list(map(int, input().split()))

sum_a = [0]
sum_b = [0]

for i in range(N):
    sum_a.append(sum_a[-1] + desk_a[i])
for i in range(M):
    sum_b.append(sum_b[-1] + desk_b[i])

ans = 0
j = M
for i in range(N+1): 
    a = sum_a[i]
    if K - a < 0:
        break
    while sum_b[j] > K - a: 
        j -= 1
    ans = max(ans, i+j)

print(ans)
import itertools

L = int(input(), 2)

count = 1
# (a, b)の組み合わせ
#products = itertools.product(range(L+1), range(L+1))
products = list(itertools.combinations(range(L+1), 2))
for p in products:
    s = p[0] + p[1]
    if s <= L:
        # XOR
        if s == (p[0] ^ p[1]):
            count += 1
            if p[0] != p[1]:
                count += 1

print(count % (10**9 + 7))

### FIXED CODE ###

L=input()
length=len(L)
inf=10**9+7
a=2
b=1
for i in range(1,len(L)):
	if L[i]=="0":
		b=b*3%inf
		continue
	else:
		b=(b*3+a)%inf
		a=a*2%inf
print((a+b)%inf)
import sys

N = int(input())
H = [int(x) for x in input().split()]

flag = 0

for i in range(len(H) - 1):
    if H[i] > H[i+1] + 1:
        print('No')
        sys.exit()
	
    elif H[i] == H[i+1] + 1:
	flag = 1
	
    if flag == 1:
        if H[i]	> H[i+1]:
            print('No')
            sys.exit()

print('Yes')

### FIXED CODE ###

import sys
N = int(input())
H = [int(x) for x in input().split()]

flag = 0
key = 0

for i in range(len(H)-1):
    if flag == 1:
        if H[i+1] < key:
            print('No')
            sys.exit()

    if i < len(H) - 1:
        if H[i] > H[i+1] + 1:
            print('No')
            sys.exit()

        elif H[i] == H[i+1] + 1:
            flag = 1
            key = H[i+1]
	
print('Yes')
from itertools import combinations
from heapq import heappush, heappop

def dist(p1, p2): return ((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2) ** 0.5
    
xs, ys, xt, yt = map(int, input().split())
N = int(input())
P = [[(xs, ys), 0, 0], [(xt, yt), 0, 1]]
for i in range(2, N+2):
    x, y, r = map(int, input().split())
    P.append([(x, y), r, i])
E = [[float('inf')] * N for _ in range(N+2)]
for v in range(N): E[v][v] = 0
for [p1, r1, i], [p2, r2, j] in combinations(P, 2):
    d = max(0, dist(p1, p2) - (r1 + r2))
    E[i][j] = E[j][i] = d
dist = [float('inf')] * N # the distance of each vertex from s
prev = [-1] * N # the previous vertex of each vertex on a shortest path from s
visited = [False] * N
n_visited = 0 # #(visited vertices)
heap = []
heappush(heap, (0, -1, 0))
while heap:
    d, p, v = heappop(heap)
    if visited[v]: continue # (s,v)-shortest path is already calculated
    dist[v] = d; prev[v] = p; visited[v] = True
    n_visited += 1
    if n_visited == N: break
    for u in range(N):
        if visited[u]: continue
        temp = d + E[v][u]
        if dist[u] > temp: heappush(heap, (temp, v, u))
print(dist[1])

### FIXED CODE ###

from itertools import combinations
from heapq import heappush, heappop

class Dijkstra:
    def __init__(self, N):
        self.N = N # #vertices
        self.E = [[] for _ in range(N)]

    def add_edge(self, init, end, weight, undirected=False):
        self.E[init].append((end, weight))
        if undirected: self.E[end].append((init, weight))
    
    def distance(self, s):
        INF = float('inf')
        E, N = self.E, self.N
        self.dist = dist = [INF] * N # the distance of each vertex from s
        self.prev = prev = [-1] * N # the previous vertex of each vertex on a shortest path from s
        dist[s] = 0
        n_visited = 1 # #(visited vertices)
        heap = []
        heappush(heap, (0, s))
        while heap:
            d, v = heappop(heap)
            if dist[v] < d: continue
            for u, c in E[v]:
                temp = d + c
                if dist[u] > temp:
                    dist[u] = temp; prev[u] = v
                    heappush(heap, (temp, u))
            n_visited += 1
            if n_visited == N: break
        return dist
    
    def shortest_path(self, t):
        P = []
        prev = self.prev
        while True:
            P.append(t)
            t = prev[t]
            if t == -1: break
        return P[::-1]

def dist(p1, p2): return ((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2) ** 0.5
    
xs, ys, xt, yt = map(int, input().split())
N = int(input())
P = [[(xs, ys), 0, 0], [(xt, yt), 0, 1]]
for i in range(2, N+2):
    x, y, r = map(int, input().split())
    P.append([(x, y), r, i])
dk = Dijkstra(N+2)
for [p1, r1, i], [p2, r2, j] in combinations(P, 2):
    d = max(0, dist(p1, p2) - (r1 + r2))
    dk.add_edge(i, j, d, undirected=True)
print(dk.distance(0)[1])
n, m, q = map(int, input().split())
cum = [[0]
for i in range(m):
    li, ri = map(int, input().split())
    lis.append(li)
    ris.append(ri)

for i in range(q):
    pi, qi = map(int, input().split())
    total = 0
    for (li, ri) in zip(lis, ris):
        if pi <= li and ri <= qi:
            total += 1
    print(total)



### FIXED CODE ###

n, m, qq = map(int, input().split())
lr = [[0] * n for _ in range(n)]
for _ in range(m):
    l, r = map(int, input().split())
    lr[l - 1][r - 1] += 1

for i in range(n):
    for j in range(n - 1):
        lr[i][j + 1] += lr[i][j]
for j in range(n):
    for i in range(n-1, 0, -1):
        lr[i - 1][j] += lr[i][j]

for _ in range(qq):
    p, q = map(int, input().split())
    if q == n:
        print(lr[p - 1][q - 1])
    else:
        print(lr[p - 1][q - 1] - lr[q][q - 1])
if a%2 == 0:
    print("0.5")
else:
    print((a//2+1)/a)

### FIXED CODE ###

a = int(input())
if a%2 == 0:
    print("0.5")
else:
    print((a//2+1)/a)
N, K = map(int,input().split())

inf = 10*9
H = [inf]*inf
for i in range(N):
    H[i] = int(input())

H.sort()
ans = inf
for i in range(N):
    ans = min(ans, H[i+K-1]-H[i])

print(ans)

### FIXED CODE ###

N, K = map(int,input().split())

H = []
for i in range(N):
    H.append(int(input()))

H.sort()
ans = 10**9
for i in range(N-K+1):
    ans = min(ans, H[i+K-1]-H[i])

print(ans)
def get():
    return list(map(int, input().split()))


a = get()
b = a[0]
c = a[1]
if b < c:
    if abs(b - c) < b:
        print(abs(b - a))
    else:
        print(b)
else:
    if a[0] % a[1] == a[1] or a[0] % a[1] == 0:
        print(0)
    else:
        if abs(a[0] % a[1] - a[1]) < abs((a[0] % a[1] - a[1]) % a[1]):
            print(abs(a[0] % a[1] - a[1]))
        else:
            print(abs((a[0] % a[1] - a[1]) % a[1]))


### FIXED CODE ###

import sys
# 未解決(最後だけREになる)


def get():
    return list(map(int, input().split()))


a = get()
b = a[0]
c = a[1]
if b < c:
    if abs(b - c) < b:
        print(abs(b - c))
        sys.exit(0)
    else:
        print(b)
        sys.exit(0)
else:
    if a[0] % a[1] == a[1] or a[0] % a[1] == 0:
        print(0)
        sys.exit(0)
    else:
        if abs((a[0] % a[1]) - a[1]) < abs(((a[0] % a[1]) - a[1]) % a[1]):
            if abs(a[0] % a[1]) < abs((a[0] % a[1]) - a[1]):
                print(abs(a[0] % a[1]))
                sys.exit(0)
            else:
                print(abs((a[0] % a[1]) - a[1]))
                sys.exit(0)
        else:
            if abs(a[0] % a[1]) < abs(((a[0] % a[1]) - a[1]) % a[1]):
                print(abs(a[0] % a[1]))
                sys.exit(0)
            else:
                print(abs(((a[0] % a[1]) - a[1]) % a[1]))
                sys.exit(0)
n,m=map(int,input().split())

h=list(map(int,input().split()))
low=[]
high=[]

for i in range(m):

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

    if h[a-1]>h[b-1]:

        low.append(b)
        high.append(a)

    elif h[a-1]==h[b-1]:


        low.extend([a,b])

    elif h[a-1]<h[b-1]:

        low.append(a)
        high.append(b)

common=list(set(low)&set(high))

for k in range(len(common)):

    high.remove(common[k])

lh_or=list(set(low) ^ set(high))

g=n-len(lh_or)
high=list(set(high))

print(len(high)+g)


### FIXED CODE ###

s=input()

if s=="ARC":

    print("ABC")

else:
    print("ARC")
import numpy as np
num = int(input())
each_num = list(map(int, input().split(" ")))

i = 1
ans = [[]]
while i >= num:
    ans.append = each_num.index(i)

print(ans)

### FIXED CODE ###

n = int(input())
l = list(map(int, input().split(" ")))
a =[0]*n

for i in range(n):
    #print(i)
    a[l[i]-1] = i + 1 #each_numのi番目のインデックスに代入, -1 はi 番目が1,2,3 ...

for i in range(n):
    print(a[i], end = " ")
R,G,B,N = (int(i) for i in input().split())
cnt = 0
for r in range(3001):
  for g in range(3001):
    V = r * R + g * G 
    if N >= V and (N - V) % == 0:
        cnt += 1
    else:
        continue
print(cnt)

### FIXED CODE ###

R,G,B,N = map(int,input().split())
cnt = 0
for r in range((N // R) + 1):
    for g in range((N - (r * R)) // G + 1):
        V = N - (r * R + g * G)
        if V >= 0 and V % B == 0:
            cnt += 1
print(cnt)
s = input()

if(s[1]==a[2]):
    print('Yes')
else:
    print('No')

### FIXED CODE ###

s = input()

if(s[1]==s[2]):
    if(s[1]==s[3] or s[1]==s[0]):
        print('Yes')
    else:
        print('No')
else:
    print('No')
from math import factorial
def comb(n,r=2):
    if n == 1 or n == 0:
        return 0
    return int(factorial(n) / factorial(r) / factorial(n - r))

n = int(input())
a = list(map(int, input().split()))

count = {}
ans = 0

for i in range(n):
    count.setdefault(a[i], 0)
    count[a[i]] += 1

for v in count.values():
    ans += comb(v)


for i in range(n):
    v = count[a[i]]
    print(ans - comb(v) + comb(v-1))

### FIXED CODE ###

from math import factorial
def comb(n):
    if n == 1 or n == 0:
        return 0
    return int(n * (n-1) / 2 )

n = int(input())
a = list(map(int, input().split()))

count = {}
ans = 0

for i in range(n):
    count.setdefault(a[i], 0)
    count[a[i]] += 1

for v in count.values():
    ans += comb(v)


for i in range(n):
    v = count[a[i]]
    print(ans - comb(v) + comb(v-1))
N = int(input())

s=[]
x = [[0 for i in range(24)] for j in range(N)]
#print(x)


for n in range(N):
    tmp=list(input())
    tmp.sort()
    s.append(tmp)

    tmp2 = set(tmp)
    for l in tmp2:
        #print(n, ord(l)-97,l,  tmp.count(l))
        x[n][ord(l)-97]= tmp.count(l)

ans  =[]
for i in range(len(x)):
    tmp3 = [row[i] for row in x]
    tmp4 = chr(97+i)* min(tmp3) if min(tmp3) != 0 else ""
    ans.append(tmp4)

print("".join(ans))

### FIXED CODE ###

N = int(input())

# 二次元配列の初期化
# 0番目をaの出現回数、
# 1番目をbの出現回数とする
x = [[0 for i in range(26)] for j in range(N)]
#print(x)

for n in range(N):
    tmp=list(input())
    # 文字列をソートする
    tmp.sort()

    # 重複排除して、それぞれの文字が何回出現したかを数える
    tmp2 = set(tmp)
    for l in tmp2:
        #print(n, ord(l)-97,l,  tmp.count(l))
        x[n][ord(l)-97]= tmp.count(l)

ans  =[]
# a~zまで調べていき、全員最低1回以上出していれば、
# その文字は出力する。最低出現回数分連続させる。
for i in range(26):
    tmp3 = [row[i] for row in x]
    tmp4 = chr(97+i)* min(tmp3) if min(tmp3) != 0 else ""
    ans.append(tmp4)

print("".join(ans))
UF=[i for i in range(100001)]
def u(a,b):
    UF[f(a)] = UF[f(b)]

def f(c):
    if(c==UF[c]):
        return c
    else:
        UF[c]=f(UF[c])
        return UF[c]

n = input()
cities = [map(int,raw_input().split(" "))+[i] for i in range(n)]

cities_x = sorted(cities, key=lambda a:a[0])
cities_y = sorted(cities, key=lambda a:a[1])

road = [[cities_x[i+1][0]-cities_x[i][0],cities_x[i][2],cities_x[i+1][2]] for i in range(n-1)]
road +=[[cities_y[i+1][1]-cities_y[i][1],cities_y[i][2],cities_y[i+1][2]] for i in range(n-1)]

sum = 0
for (cost,i,j) in sorted(road):
    if(f(i)!=f(j)):
        u(i,j)
        sum += cost

print sum


### FIXED CODE ###

class UnionFind3:
    def __init__(self, size):
        self.table = [-1 for _ in xrange(size)]

    def find(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self.find(self.table[x])
            return self.table[x]

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False

uf=UnionFind3(100001)

n = input()
cities = [map(int,raw_input().split(" "))+[i] for i in range(n)]

cities_x = sorted(cities, key=lambda a:a[0])
cities_y = sorted(cities, key=lambda a:a[1])

road = [[cities_x[i+1][0]-cities_x[i][0],cities_x[i][2],cities_x[i+1][2]] for i in range(n-1)]
road +=[[cities_y[i+1][1]-cities_y[i][1],cities_y[i][2],cities_y[i+1][2]] for i in range(n-1)]

sum = 0
for (cost,i,j) in sorted(road):
    if(uf.find(i)!=uf.find(j)):
        uf.union(i,j)
        sum += cost

print sum
n=int(input())
s=list(input())
k=int(input())
for i in s:
      if i != s[k-1]:
          s_replace=s.replace(i,'*')
print(s_replace)

### FIXED CODE ###

n=int(input())
s=input()
k=int(input())

for a in s:
    if a==s[k-1]:
          print(a,end='')
    else:
          print('*',end='')
from functools import reduce

def fib_memo(n):
  memo = [0]*(n+1)
  def _fib(n):
    if n <= 1:
      return n
    if memo[n] != 0:
      return memo[n]
    memo[n] = _fib(n-1) + _fib(n-2)
    return memo[n]
  return _fib(n)

N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
B = [0]*(M + 1)
for i in range(M+1):
  if i == 0:
    diff = A[i] - 1
    B[0] = fib_memo(diff + 1)
  elif i == M:
    diff = N - A[M - 1] -1
    B[M] = fib_memo(diff + 1)
  else:
    diff = A[i] - A[i-1]
    if diff == 1:
      B[i] = 0
      break
    B[i] = fib_memo(diff + 1)
Ans = reduce(lambda a, b: a*b, B)
print(Ans % 1000000007)

### FIXED CODE ###

N, M = map(int, input().split())
A = [True] * (N+1)
for _ in range(M):
  idx = int(input())
  A[idx] = False

step = [0] * (N+1)
step[0] = 1
for i in range(1, N+1):
  if A[i]:
    step[i] = step[i-1] + step[i-2]
  else:
    step[i] = 0
print(step[N]%(10**9+7))
import numpy as np

inp = np.asarray(input().split(), dtype=int)
inp = np.sort(inp)
print(inp[0]*10+np.sum(inp[1:])

### FIXED CODE ###

import numpy as np
 
inp = np.asarray(input().split(), dtype=int)
inp = np.sort(inp)
print(np.sum(inp)+inp[2]*9)
import math

def is_prime(n):
    if n == 1: return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True

n=int(input())

x=n
for i in range(n,10**5): 
   if is_prime(i):
       break


print (i) 



### FIXED CODE ###

import math

def is_prime(n):
    if n == 1: return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True

n=int(input())

x=n
for i in range(n,10**6): 
   if is_prime(i):
       break


print (i)
n = list(map(int, input().split()))
if(n[1] == 0):
  print(n[0])
  exit()
x = list(map(int, input().split()))
print(n)
print(type(x))
  
for i in range(1,100):
  if(('n[0] - i' in x) == False):
    print(n[0] - i)
    exit()
  elif(('n[0] + i' in x) == False):
    print(n[0] + i)
    exit()

### FIXED CODE ###

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

for i in range(5):
  if(n[i] != i+1):
    print(i+1)
    exit()
n = int(input())

c = 0

ans = 'No'
for i in range(15):
    for i in range(26):
        c = 4 * j + 7 * i
    if n == c:
        ans = 'Yes'

print(ans)

### FIXED CODE ###

n = int(input())

c = 0

ans = 'No'

for i in range(15):
    for j in range(26):
        c = 4 * j + 7 * i
        if n == c:
            ans = 'Yes'
            break
print(ans)