Harryxun/stf_run huggingface dataset:
import sys,bisect
input = sys.stdin.readline

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

ans = [1]*n

edge = [[] for i in range(n)]
for i in range(n-1):
    u,v = map(int,input().split())
    edge[u-1].append(v-1)
    edge[v-1].append(u-1)

root = 0
chi = [[] for i in range(n)]
par = [-1]*n
used = [False]*n
tank = [0]

while tank:
    q = tank.pop()
    used[q] = True
    for e in edge[q]:
        if not used[e]:
            chi[q].append(e)
            tank.append(e)
            par[e] = q

tank = [root]

idx = dict()
val = dict()
dp = [10**6]*n

eulerNum = -1

while tank:
    q = tank.pop()
    if q >= 0:
        #first time
        num = a[q]
        kk = bisect.bisect_left(dp,num)
        val[q] = dp[kk]
        idx[q] = kk
        dp[kk] = num
        ans[q] = kk+1

        eulerNum += 1
        tank.append(~q)
        for ch in chi[q]:
            tank.append(ch)
    else:
        if ~q != root:
            dp[idx[~q]] = val[~q]
            eulerNum += 1

print(*ans,sep = "\n")

### FIXED CODE ###

import sys,bisect
input = sys.stdin.readline

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

ans = [1]*n

edge = [[] for i in range(n)]
for i in range(n-1):
    u,v = map(int,input().split())
    edge[u-1].append(v-1)
    edge[v-1].append(u-1)

root = 0
chi = [[] for i in range(n)]
par = [-1]*n
used = [False]*n
tank = [0]

while tank:
    q = tank.pop()
    used[q] = True
    for e in edge[q]:
        if not used[e]:
            chi[q].append(e)
            tank.append(e)
            par[e] = q

tank = [root]

idx = dict()
val = dict()
dp = [10**10]*n

eulerNum = -1

while tank:
    q = tank.pop()
    if q >= 0:
        #first time
        num = a[q]
        kk = bisect.bisect_left(dp,num)
        
        val[q] = dp[kk]
        idx[q] = kk
        dp[kk] = num
        ans[q] = bisect.bisect_left(dp,10**10)

        eulerNum += 1
        tank.append(~q)
        for ch in chi[q]:
            tank.append(ch)
    else:
        if ~q != root:
            if dp[idx[~q]] == a[~q]:
                dp[idx[~q]] = val[~q]
                eulerNum += 1

print(*ans,sep = "\n")
from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
#N=int(input())
#S=[list(map(int,input().split())) for i in range(N)]
idle=10**13
xs,ys,xt,yt=map(int,input().split())
N=int(input())
XYR=[list(map(int,input().split())) for i in range(N)]
XYR.append([xt,yt,0])#終点
XYR.append([xs,ys,0])#開始
"""for i in range(len(XYR)):
    XYR[i][0]*=idle
    XYR[i][1]*=idle
    XYR[i][2]*=idle"""
kyori=[[0 for i in range(len(XYR))] for n in range(len(XYR))]
for i in range(len(XYR)):
    for m in range(i,len(XYR)):
        if i==m:
            t=0
        else:
            x1,y1,r1=XYR[i]
            x2,y2,r2=XYR[m]
            t=max(((x2-x1)**2+(y2-y1)**2)**.5-r1-r2,0)

        kyori[i][m]=round(t*idle)
        kyori[m][i]=round(t*idle)

stack=sorted(kyori[-2])
heapify(stack)
Pdic={}
dic={}
kyoriset=set()
for i in range(len(XYR)):
    a=kyori[-1][i]
    Pdic.update({i:a})
    if not a in kyoriset:
        kyoriset.add(a)
        dic.update({a:[i]})
    else:
        dic[a].append(i)
visited=set([len(XYR)-1])
while stack:
    m=heappop(stack)
    a=dic[m].pop()
    if a==len(XYR)-2:
        print(m/idle)
        exit()
    if not a in visited:
        visited.add(a)
        for i in range(len(XYR)):
            nm=kyori[a][i]+m
            if Pdic[i]>nm:
                Pdic[i]=nm
                heappush(stack,nm)
                if not nm in kyoriset:
                    kyoriset.add(nm)
                    dic.update({nm:[i]})
                else:
                    dic[nm].append(i)


### FIXED CODE ###

from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
#N=int(input())
#S=[list(map(int,input().split())) for i in range(N)]
idle=10**13
xs,ys,xt,yt=map(int,input().split())
N=int(input())
XYR=[list(map(int,input().split())) for i in range(N)]
XYR.append([xt,yt,0])#終点
XYR.append([xs,ys,0])#開始
"""for i in range(len(XYR)):
    XYR[i][0]*=idle
    XYR[i][1]*=idle
    XYR[i][2]*=idle"""
kyori=[[0 for i in range(len(XYR))] for n in range(len(XYR))]
for i in range(len(XYR)):
    for m in range(i,len(XYR)):
        if i==m:
            t=0
        else:
            x1,y1,r1=XYR[i]
            x2,y2,r2=XYR[m]
            t=max(((x2-x1)**2+(y2-y1)**2)**.5-r1-r2,0)

        kyori[i][m]=t
        kyori[m][i]=t
stack=sorted(kyori[-1])
heapify(stack)
Pdic={}
dic={}
kyoriset=set()
for i in range(len(XYR)):
    a=kyori[-1][i]
    Pdic.update({i:a})
    if not a in kyoriset:
        kyoriset.add(a)
        dic.update({a:[i]})
    else:
        dic[a].append(i)
visited=set([len(XYR)-1])
while stack:
    m=heappop(stack)
    a=dic[m].pop()
    if a==len(XYR)-2:
        print(m)
        exit()
    if not a in visited:
        visited.add(a)
        for i in range(len(XYR)):
            nm=kyori[a][i]+m
            if Pdic[i]>nm:
                Pdic[i]=nm
                heappush(stack,nm)
                if not nm in kyoriset:
                    kyoriset.add(nm)
                    dic.update({nm:[i]})
                else:
                    dic[nm].append(i)
#C
from math import gcd
A,B=map(int,input().split())
LCM=A*B/gcd(A,B)
print(int(LCM))

### FIXED CODE ###

#C
A,B=map(int,input().split())
GCD=1
for i in range(2,10**5+1):
    if A%i==0 and B%i==0:
        GCD=i

LCM=A*B/GCD
print(int(LCM))
N=int(input())
A=list(map(int,input().split()))
def f(i):
  if i==0:
    return 1
  else:
    return f(i-1)*A[i-1]
a=f(N)
print(a if a<=10**(18) else -1)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
a=1
k=0
if 0 in A:
  print(0)
else:
  for i in range(N):
    a*=A[i]
    if a>10**(18):
      k=1
      break
  if k==1:
    print(-1)
  else:
    print(a)
n, q = map(int, input().split())

#print(n,q)
edge = []
for i in range(n-1):
    a = list(map(int, input().split()))
    edge.append(a)

add_list = []
for i in range(q):
    p = list(map(int, input().split()))
    add_list.append(p)

#print(edge,add_list)


dir_edge = [[] for i in range(n)]

for e in edge:
    dir_edge[e[0]-1].append(e[1]-1)
    dir_edge[e[1]-1].append(e[0]-1)
#print(dir_edge)


add_value = [0]*n
for v in add_list:
    add_value[v[0]-1] += v[1]
#print(add_value)


dp = [-1] * n

def dfs(index, parent,value):
    if (dp[index] != -1):
        return dp[index]
    value += add_value[index]
    dp[index] = value
    for i in dir_edge[index]:
        if (parent == i):
            continue
        dfs(i,index,value)
        

dfs(0, -1, 0)
print(dp)

### FIXED CODE ###

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

#print(n,q)
edge=[]
for i in range(n-1):
    a = list(map(int,input().split()))
    edge.append(a)

add_list = []
for i in range(q):
    p = list(map(int,input().split()))
    add_list.append(p)

#print(edge,add_list)

ans = [0] * n
edge_list = [-1] * n

for e in edge:
    edge_list[e[1]-1] = e[0]-1

add_value = [0]*n
for v in add_list:
    add_value[v[0]-1] += v[1]

#print(edge_list)
#print(add_value)


dp = [-1] * n
def get_value(i):
    if(dp[i]!=-1):
        return dp[i]
    tmp = add_value[i]
    if edge_list[i] != -1:
        tmp += get_value(edge_list[i])
    dp[i] = tmp
    return dp[i]

for i in range(n):
    ans[i] = get_value(i)
    #print(i,ans)

print(' '.join(map(str,ans)))
n,a,b,c,d=map(int,input().split())
s=list(input())
f=0
for i in range(b,d-1):
  if s[i]=='#' and s[i+1]=='#':
    f=1
    break
for i in range(a,c-1):
  if s[i]=='#' and s[i+1]=='#':
    f=1
    break
if c>d:
  F=0
  for i in range(b-1,d):
    if s[i]=='.' and s[i+1]=='.' and s[i+2]=='.':
      F=1
      break
  if F==0:
    f=1
if f==1:print('No')
else:print('Yes')

### FIXED CODE ###

n,a,b,c,d=map(int,input().split())
s=list(input())
if c<d:
  f=0
  for i in range(b,d-1):
    if s[i]=='#' and s[i+1]=='#':
      f=1
      break
  if f==0:
    for i in range(a,c-1):
      if s[i]=='#' and s[i+1]=='#':
        f=1
        break
  if f==1:print('No')
  else:print('Yes')
else:
  f=0
  for i in range(b,d-1):
    if s[i]=='#' and s[i+1]=='#':
      f=1
      break
  if f==0:
    for i in range(a,c-1):
      if s[i]=='#' and s[i+1]=='#':
        f=1
        break
  if f==0:
    if (s[d-2]=='#' or s[d]=='#') and (s[b-2]=='#' or s[b]=='#'):
      ct=0
      for i in range(b-1,d-2):
        if s[i]=='.' and s[i+1]=='.' and s[i+2]=='.':
          ct+=1
          break
      if ct==0:
        f=1
  if f==1:print('No')
  else:print('Yes')
# 文字列の入力
O = char(input())
E = char(input())

L = len(O)
TMP = ""

for i in 0:L:
    TMP = str(TMP+O[i]+E[i])

print(TMP)

### FIXED CODE ###

# 文字列の入力
O = input()
E = input() + " "

L = len(O)
TMP = ""

for i in range(L):
    TMP = TMP+O[i]+E[i]

print(TMP.strip())
import bisect
n=int(input())
A=sorted(list(map(int,input().split())))
B=sorted(list(map(int,input().split())))
C=sorted(list(map(int,input().split())))
print(sum(bisect.bisect_left(A,b)*(N-bisect.bisect_right(C,b)) for b in B))

### FIXED CODE ###

import bisect
n=int(input())
A=sorted(list(map(int,input().split())))
B=sorted(list(map(int,input().split())))
C=sorted(list(map(int,input().split())))
print(sum(bisect.bisect_left(A,b)*(n-bisect.bisect_right(C,b)) for b in B))
import sys

n, k = map(int, raw_input().split())
ans = k # first                                                                                                 
if n = 1 and k = 1:
    print ans
    sys.exit()
for i in range(n-1):
    ans *= k-1



### FIXED CODE ###

import sys

n, k = map(int, raw_input().split())
ans = k # first                                                                                                 
if n == 1 and k == 1:
    print ans
    sys.exit()
for i in range(n-1):
    ans *= k-1
print ans
a,b = map(str, input().split())
print(b+s)

### FIXED CODE ###

a,b = map(str, input().split())
print(b+a)
s = input()[::-1]

def solve(s):
    if s in ["maerd","remaerd","esare","resare"]:
        return True
    elif len(s) <= 7:
        return False
    if s[0:5] in ["maerd","esare"]:
        return solve(s[5:])
    if s[0:6] == "resare":
        return solve(s[6:])
    if s[0:7] == "remaerd":
        return solve(s[7:])
    return False
print("YES" if solve(s) else "NO")

### FIXED CODE ###

s = input()[::-1]
flag = 1
i = 0
while i < len(s):
    if s[i:i+5] == "maerd" or s[i:i+5] == "esare":
        i += 5
    elif s[i:i+6] == "resare":
        i += 6
    elif s[i:i+7] == "remaerd":
        i += 7
    else:
        flag = 0
        break

print("YES" if flag else "NO")
n, q = map(int, input().split())
#n, q = map(int, "4 3".split())

g = [[] for _ in range(n)]

for i in range(n-1):
    a, b = map(int, input().split())
    #a, b = map(int, ["1 2", "2 3", "2 4"][i].split())
    g[a-1] += append(b-1)

ans = [0] * n
def dfs(start, point):
    stack = [start]
    while stack:
        x = stack.pop()
        ans[x] += point
        stack += g[x]

for i in range(q):
    p, v = map(int, input().split())
    #p, v = map(int, ["2 10", "1 100", "3 1"][i].split())
    dfs(p-1, v)

print(' '.join(map(str, ans)))


### FIXED CODE ###

import sys

def main():
    sys.setrecursionlimit(10**6)
    input = sys.stdin.readline
    n, q = map(int, input().split())
    #n, q = map(int, "4 3".split())
    g = [[] for _ in range(n)]
    for i in range(n-1):
        a, b = map(int, input().split())
        #a, b = map(int, ["1 2", "2 3", "2 4"][i].split())
        g[a-1].append(b-1)
        g[b-1].append(a-1)


    add = [0] * n
    for i in range(q):
        p, v = map(int, input().split())
        #p, v = map(int, ["2 10", "1 100", "3 1"][i].split())
        #dfs(p-1, v)
        add[p-1] += v

    ans = [0] * n
    def dfs(v,p,value): #p: parent of v
        value += add[v]
        ans[v] = value
        for c in g[v]:
            if c == p: continue
            dfs(c,v,value)
    dfs(0, -1, 0)
    """
    def dfs(start, point):
        stack = [start]
        while stack:
            x = stack.pop()
            ans[x] += point
            stack += g[x]
    """

    print(' '.join(map(str, ans)))

if __name__ == '__main__':
    main()
from functools import reduce
def cmb(n,r):
    numerator = reduce(lambda x, y: x * y % mod, [n - r + k + 1 for k in range(r)])
    denominator = reduce(lambda x, y: x * y % mod, [k + 1 for k in range(r)])
    return numerator * pow(denominator, mod - 2, mod) % mod

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

# ans=imp_pow(2,n)-1
ans=pow(2,c,10**9+7)-1
ans-=cmb(n,a)
ans-=cmb(n,b)
print(ans%10**9+7)

### FIXED CODE ###

from functools import reduce
def cmb(r):
    numerator = reduce(lambda x, y: x * y % mod, [n - r + k + 1 for k in range(r)])
    denominator = reduce(lambda x, y: x * y % mod, [k + 1 for k in range(r)])
    return numerator * pow(denominator, mod - 2, mod) % mod
n,a,b = map(int,(input().split()))
ans=0
mod=10**9+7

ans=pow(2,n,10**9+7)-1
ans-=cmb(a)
ans-=cmb(b)
print(ans%mod)
# coding: utf-8


def main():
    n = int(input())

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

    for coordinate in coordinates:
        if coordinate[2] > 0:
            xx = coordinate[0][0]
            yy = coordinate[0][1]
            hh = coordinate[0][2]
            break

    for px in range(101):
        for py in range(101):
            ph = hh + abs(xx - px) + abs(yy - py)

            if ph <= 0:
                continue

            suit = True
            for coordinate in coordinates:
                if coordinate[2] != ph - abs(coordinate[0] - px) - abs(coordinate[1] - py):
                    suit = False
                    break

            if suit == True:
                print(px, py, ph)
                return


if __name__ == '__main__':
    main()


### FIXED CODE ###

# coding: utf-8


def main():
    n = int(input())

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

    for coordinate in coordinates:
        if coordinate[2] > 0:
            xx = coordinate[0]
            yy = coordinate[1]
            hh = coordinate[2]
            break

    for px in range(101):
        for py in range(101):
            ph = hh + abs(xx - px) + abs(yy - py)

            suit = True
            for x, y, h in coordinates:
                if h != max(ph - abs(x - px) - abs(y - py), 0):
                    suit = False
                    break

            if suit == True:
                print(px, py, ph)
                return


if __name__ == '__main__':
    main()
import sys
input = sys.stdin.readline
import math

def main():
    a, b, x = [int(x) for x in input().split()]
    b_now = x / (a * a)
    menseki = b_now * a
    ans_a = menseki * 2 / b

    if ans_a <= a:
        z = math.degrees(math.atan(ans_a / b))
        print(90 - z)
        exit()
    else:
        menseki = a * b - menseki
        ans_b = menseki * 2 / a
        z = math.degrees(math.atan(a / ans_b))
        print(90 - z)
        exit()



if __name__ == '__main__':
    main()



### FIXED CODE ###

import sys
input = sys.stdin.readline
import math

def main():
    a, b, x = [int(x) for x in input().split()]
    b_now = x / (a * a)
    menseki = b_now * a
    ans_a = menseki * 2 / b

    if a * a * b == x:
        print(0)
        exit()

    if ans_a <= a:
        z = math.degrees(math.atan(ans_a / b))
        print(90 - z)
        exit()
    else:
        menseki = a * b - menseki
        ans_b = menseki * 2 / a
        z = math.degrees(math.atan(a / ans_b))
        print(90 - z)
        exit()



if __name__ == '__main__':
    main()
n = int(input())
s1 = list(map(int,input().split()))
#print(type(s1))
val1 = 0
for i in range(n):
	val1 = val1 + s1[i] * math.factorial(10-i-1) // math.factorial(10-n)
#	print(math.factorial(10-i-1) // math.factorial(10-n))
print(val1)

### FIXED CODE ###

import math

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

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

ord1 = 0
flag = [0] * (n+1)
for i in range(n-1):
	ln = 0
#	print(type(p[i]), p[i])
	for c in range(1,p[i]):
		if flag[c] == 0:
			ln = ln + 1 
	flag[p[i]] = 1
	ord1 = ord1 + ln * math.factorial(n-1-i)
#	print(ln,  math.factorial(ln))
ord1 = ord1+1 
#print(ord1)
  
ord2 = 0
flag = [0] * (n+1)
for i in range(n-1):
	ln = 0
#	print(type(q[i]), q[i])
	for c in range(1,q[i]):
		if flag[c] == 0:
			ln = ln + 1 
	flag[q[i]] = 1
	ord2 = ord2 + ln * math.factorial(n-1-i)
#	print(ln,  math.factorial(ln))
ord2 = ord2+1 
#print(ord2)

print(abs(ord2 - ord1))
n,d=[int(x) for x in input().split()]
x=[list(map(int,input().split())) for i in range(n)]
answer = 0
for i in range(n):
  for j in range(i+1,n):
    v = (x[i][0]-x[j][0])**2+(x[i][1]-x[j][1])**2
    k = 1
    while k**2<=v:
      if k**2 == v:
        answer += 1
        break
      k += 1
print(answer)

### FIXED CODE ###

n,d=[int(x) for x in input().split()]
x=[list(map(int,input().split())) for i in range(n)]
answer = 0
for i in range(n):
  for j in range(i+1,n):
    v = 0
    for k in range(d):
    	v += (x[i][k]-x[j][k])**2
    	t = 1
    while t**2<=v:
      	if t**2 == v:
        	answer += 1
        	break
      	t += 1
print(answer)
import math
n = int(input())

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

L = factorization(math.factorial(n))

out = 1
for i in range(len(L)):
  out = out * (L[i][1] + 1)
print(out)


### FIXED CODE ###

import math
n = int(input())
outlist = [0 for i in range(n+1)]

def isprime(n):
  for i in range(2, int(math.sqrt(n)+1)):
    if n%i == 0:
      return (0)
      break
  return (1)
    
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
 
    if temp!=1:
        arr.append([temp, 1])
 
    if arr==[]:
        arr.append([n, 1])
 
    return arr 

for i in range(2,n+1):
  L = factorization(i)
  for j in range(len(L)):
    if isprime(L[j][0]) == 1:
      outlist[L[j][0]] += L[j][1]

out = 1
for i in range(len(outlist)):
  out = out * (outlist[i]+1)
print(out % (pow(10,9)+7))
n,m = map(int,input().split())
s = [list(map(int,input().split())) for _ in range(m)]
p = list(map(int,input().split()))
res = 0

for i in range(2**n):
    ptn = format(i, 'b').rjust(n, '0')
    light = True
    for j in range(m):
        tmp = 0
        for n in range(1, s[j][0]+1):
            if ptn[s[j][n] - 1] == '1':
                tmp += 1
        if tmp%2 != p[j]:
            light = False
    if light:
        res += 1
print(res)

### FIXED CODE ###

N,M = map(int,input().split())
s = [list(map(int, input().split())) for _ in range(M)]
p = list(map(int, input().split()))
ans = 0

for i in range(2**N):
    ptn = bin(i)[2:].rjust(N,'0')
    light = True
    for j in range(M):
        tmp = 0
        for n in range(1,s[j][0] + 1):
            if ptn[s[j][n]-1]=='1':
                tmp += 1
        if tmp % 2 != p[j] % 2:
            light = False
    if light:
        ans += 1
print(ans)
n, y = map(int, input().split())

a = -1
b = -1
c = -1

for i in range(n):
  for t in range(i, n):
    sum = 10000 * i + 5000 * (t - i)  + 1000 * (n - t)
    if sum == y:
      a = i
      b = t - i
      c = n - t
      
print(x, y, z)

### FIXED CODE ###

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

a = -1
b = -1
c = -1

for i in range(n + 1):
  for t in range(i, n + 1):
    sum = 10000 * i + 5000 * (t - i)  + 1000 * (n - t)
    if sum == y:
      a = i
      b = t - i
      c = n - t
      
print(a, b, c)
h,w=map(int,input().split())
s=[input() for i in range(h)]

ans=[]
for i in range(h):
  if s[i]!='.'*w:
    ans.append(s[i])

n=len(ans)
a=['' for i in range(n)]

for i in range(w):
  sm=''
  cnt=0
  for j in range(n):
    sm+=ans[j][i]
    if ans[j][i]!='.':
      cnt+=1
  if cnt!=0:
    for k in range(n):
      a[k]+=ans[k][i]
m=len(a[0])
for i in range(m):
  print(a[i])

### FIXED CODE ###

h,w=map(int,input().split())
s=[input() for i in range(h)]

ans=[]
for i in range(h):
  if s[i]!='.'*w:
    ans.append(s[i])

n=len(ans)
a=['' for i in range(n)]

for i in range(w):
  sm=''
  cnt=0
  for j in range(n):
    sm+=ans[j][i]
    if ans[j][i]!='.':
      cnt+=1
  if cnt!=0:
    for k in range(n):
      a[k]+=ans[k][i]
m=len(a)
for i in range(m):
  print(a[i])
a,b,c = input().split( )
area = int(a*b /2)
print(area)

### FIXED CODE ###

a,b,c = map(int, input().split( ))
area = int(a*b /2)
print(area)
import math
X = int(input())
Y = 100
count = 0
while Y =< X:
    Y = math.floor(Y * 1.01)
    count += 1

print(count)



### FIXED CODE ###

import math
X = int(input())
Y = 100
count = 0
while Y < X:
    Y = Y + Y // 100
    count += 1

print(count)
while True:
  h, w = map(int, input().split())
  if not h:
    break

  mp = [list("X" + input() + "X") for _ in range(h)]
  mp.insert(0, ["X"] * (w + 2))
  mp.append(["X"] * (w + 2))
  
  direct = ((0, 1), (0, -1), (1, 0), (-1, 0))

  def search(x, y, target):
    mp[y][x] = "X"
    for dx, dy in direct:
      nx, ny = x + dx, y + dy
      if mp[ny][nx] == target:
        search(nx, ny, target)
  
  ans = 0

  for x in range(1, w + 1):
    for y in range(1, h + 1):
      target = mp[y][x]
      if target != "X":
        search(x, y, target)
        ans += 1
  
  print(ans)


### FIXED CODE ###

import sys

sys.setrecursionlimit(100000)

while True:
  h, w = map(int, input().split())
  if not h:
    break

  mp = [list("X" + input() + "X") for _ in range(h)]
  mp.insert(0, ["X"] * (w + 2))
  mp.append(["X"] * (w + 2))
  
  direct = ((0, 1), (0, -1), (1, 0), (-1, 0))

  def search(x, y, target):
    mp[y][x] = "X"
    for dx, dy in direct:
      nx, ny = x + dx, y + dy
      if mp[ny][nx] == target:
        search(nx, ny, target)
  
  ans = 0

  for x in range(1, w + 1):
    for y in range(1, h + 1):
      target = mp[y][x]
      if target != "X":
        search(x, y, target)
        ans += 1
  
  print(ans)
a=int(input()
b=a*0,000000001
print(b)

### FIXED CODE ###

a=int(input())
b=a+1
c=0
d=0
for i in range(b):
	c=i%2
	if c == 1:
		d=d+1
	else:
		pass
e=d/a
print(e)
list = input().split(" ")
N = int(list[0])
K = int(list[1])
list_hp = input().split(" ")
list_hp = [int(i) for i in list_hp]
list_hp = sorted(list_hp)

if K < N:
    for i in range(1,K+1):
        list_hp.pop(-i)
    print(sum(list_hp))
    
else:
    print(0)

### FIXED CODE ###

list = input().split(" ")
N = int(list[0])
K = int(list[1])
list_hp = input().split(" ")
list_hp = [int(i) for i in list_hp]
list_hp = sorted(list_hp)

if K < N:
    sum = 0
    for i in range(N-K):
        sum = sum + list_hp[i]
    print(sum)
else:
    print(0)
print((int(input()) - 1) * (int(input()) - 1))

### FIXED CODE ###

n, m = list(map(int, input().split()))
print((n - 1) * (m - 1))
N, M = map(int, input().split())
if M == N:
    print("Yes")
else:
    Print("No")

### FIXED CODE ###

N, M = map(int, input().split())
if M == N:
    print('Yes')
else:
    print('No')
import sys
def sign(x):
    if x>0: s=1
    elif x<0: s=-1
    else s=0
    return s

def f(p1,p2,p3):
    x1,y1 = p1
    s = sign((p3[1]-y1)*(p2[0]-x1)-(p2[1]-y1)*(p3[0]-x1))
    return s

for s in sys.stdin:
    D = map(float, s.split(","))
    p1 = D[0:2]; p2 = D[2:4]; p3 = D[4:6]; p4 = D[6:8]
    x = f(p1,p3,p2) != f(p1,p3,p4) and f(p2,p4,p1) != f(p2,p4,p3)
    print ["NO","YES"][x]

### FIXED CODE ###

import sys
def sign(x):
    if x>0: s=1
    elif x<0: s=-1
    else: s=0
    return s

def f(p1,p2,p3):
    x1,y1 = p1
    s = sign((p3[1]-y1)*(p2[0]-x1)-(p2[1]-y1)*(p3[0]-x1))
    return s

for s in sys.stdin:
    D = map(float, s.split(","))
    p1 = D[0:2]; p2 = D[2:4]; p3 = D[4:6]; p4 = D[6:8]
    x = f(p1,p3,p2) != f(p1,p3,p4) and f(p2,p4,p1) != f(p2,p4,p3)
    print ["NO","YES"][x]