ABC251～260
https://qiita.com/sano192/items/0e5c5fc9ce9ac973c2b8

ABC261～270
https://qiita.com/sano192/items/fb8d3bf7fb12690adad0

ABC271 A

# 入力の受け取り
N=int(input())
 
# 16進数に変換
N=hex(N)
 
# 2文字目以降を取り出し(「0x」を消す)
N=N[2:]
 
# 全て大文字へ変換
N=N.upper()
 
# Nの文字数が1ならば
if len(N)==1:
    # 先頭に「0」をつける
    print("0"+N)
# そうでなければ
else:
    # Nを出力
    print(N)

ABC271 B

# 入力の受け取り
N,Q=map(int,input().split())
 
# 空のリストを作る
a=[]
 
# てきとうな数列で0番目を埋める
a.append([0])
 
# N回
for i in range(N):
    # 入力の受け取り
    La=list(map(int,input().split()))
    # aに追加
    a.append(La)
 
# Q回
for i in range(Q):
    # 入力の受け取り
    s,t=map(int,input().split())
    # s番目のリストのt番目を出力
    print(a[s][t])

ABC271 C

# 入力の受け取り
N=int(input())
a=list(map(int,input().split()))
 
# 売る漫画の数
amari=0
 
# 各巻の冊数確認
count=[0]*(N+1)
 
# 持っている漫画(x巻を持っているならcomics[x]=1)
comics=[0]*(N+1)
 
# 0巻を持っている漫画とする
comics[0]=1
 
# 売る漫画と残す漫画を分ける(売る漫画の冊数を記録する)
# i=0~(N-1)
for i in range(N):
    # 巻数がN以下 かつ a[i]を持っている冊数が0
    if a[i]<=N and count[a[i]]==0:
        # 1冊持っていると記録
        count[a[i]]=1
        # a[i]は持っている漫画と記録
        comics[a[i]]=1
 
    # そうでない場合
    else:
        # 売る漫画にカウント
        amari+=1
 
# 読もうとしている漫画の巻数
i=1
# 売ろうとしている漫画の巻数
k=N
 
# i≤Nの間
while i<=N:
    # i巻を持っていなければ
    if comics[i]==0:
        # 売る漫画が2冊以上あれば
        if 2<=amari:
            # 2冊売る
            amari-=2
            # i巻を買う
            comics[i]=1
            # 次の巻へ
            i+=1
 
        # そうでなければ
        else:
            # 読もうとしている巻<売ろうとしている巻ならば
            if i<k:
                # k巻を持っているならば
                if comics[k]==1:
                    # 売る
                    amari+=1
                    # 持っている漫画から外す
                    comics[k]=0
           
            # そうでなければ
            else:
                # (i-1)巻まで読める
                print(i-1)
                # 終了
                exit()
               
            # kをマイナス1
            k-=1
   
    # そうでなければ
    else:
        # 次の巻へ
        i+=1
 
# ここまでくればi=N
# N巻まで読める
print(N)

ABC271 D

# 入力の受け取り
N,S=map(int,input().split())
 
# i番目までカードで作れる総和
# 重複を記録しないようにsetで
iSum=set()
 
# defaultdictのインポート
from collections import defaultdict
# 表裏の組み合わせ記録
# 初期値は空文字列=""
HT=defaultdict(str)
 
# 0を追加
iSum.add(0)
 
# N回
for i in range(N):
    # 入力の受け取り
    a,b=map(int,input().split())
    # 新しい和
    NewiSum=set()
    # 新しい表裏の組み合わせ
    NewHT=defaultdict(str)
 
    # x：iSumの要素それぞれ
    for x in iSum:
        # x+aを作れることを記録
        # xのまでの記録に"H"を付け加える
        NewHT[x+a]=HT[x]+"H"
        # 新しい和に(x+a)を追加
        NewiSum.add(x+a)
 
        # 裏側も同様
        NewHT[x+b]=HT[x]+"T"
        NewiSum.add(x+b)
 
    # 更新
    iSum=NewiSum
    HT=NewHT
 
# Sの組み合わせがあれば
if len(HT[S])==N:
    # 「Yes」を出力
    print("Yes")
    # 表裏の組み合わせを出力
    print(HT[S])
# そうでなければ
else:
    # 「No」を出力
    print("No")

ABC272 A

# 入力の受け取り
N=int(input())
A=list(map(int,input().split()))
 
# Aの合計を出力
print(sum(A))

ABC272 B

# 入力の受け取り
N,M=map(int,input().split())
 
# 同時に参加している人の組の記録
# (例)Pair[1][2]=1なら人1と人2が同時に参加している
Pair=[[0]*(N+1) for i in range(N+1)]
 
# M回
for i in range(M):
    # リストで受け取り
    kx=list(map(int,input().split()))
    # 0番目がk
    k=kx[0]
    # 1番目以降がx
    x=kx[1:]
 
    # a=0~(k-1)
    for a in range(k):
        # b=(a+1)~(k-1)
        for b in range(a+1,k):
            # x[a]とx[b](参加者のa番目とb番目)が同時に参加している
            Pair[x[a]][x[b]]=1
 
# a=1~N
for a in range(1,N+1):
    # b=(a+1)~N
    for b in range(a+1,N+1):
        # 人aと人bが同時に参加していなければ
        if Pair[a][b]==0:
            # 「No」を出力
            print("No")
            # 終了
            exit()
 
# 全組同時に参加していればここまで来る
# 「Yes」を出力
print("Yes")

ABC272 C

# 入力の受け取り
N=int(input())
A=list(map(int,input().split()))
 
# 偶数(even)のリスト
Ae=[]
# 奇数(odd)のリスト
Ao=[]
 
# i=0~(N-1)
for i in range(N):
    # A[i]が偶数⇔2で割った余りが0
    if A[i]%2==0:
        # 偶数リストに追加
        Ae.append(A[i])
    # そうでなければ(A[i]が奇数)
    else:
        # 奇数リストに追加
        Ao.append(A[i])
 
# 大きい順にソート
Ae.sort(reverse=True)
Ao.sort(reverse=True)
 
# 答え(初期値は-1)
ans=-1
 
# 偶数リストの長さが2以上ならば
if 2<=len(Ae):
    # ansと「(偶数の中で最も大きい)+(偶数の中で2番目に大きい)」の大きい方
    ans=max(ans,Ae[0]+Ae[1])
# 奇数リストの長さが2以上ならば
if 2<=len(Ao):
    # ansと「(奇数の中で最も大きい)+(奇数の中で2番目に大きい)」の大きい方
    ans=max(ans,Ao[0]+Ao[1])
 
# 答えの出力
print(ans)

ABC272 D

# pypyで提出
 
# 入力の受け取り
N,M=map(int,input().split())
 
# 方向の記録
d=[]
 
# a=-10^3(より少し小さめ)~10^3(より少し大きめ)
for a in range(-10**3-10,10**3+10):
    # b=-10^3(より少し小さめ)~10^3(より少し大きめ)
    for b in range(-10**3-10,10**3+10):
        # a^2+b^2=Mならば
        if a**2+b**2==M:
            # (a,b)方向へ進める
            d.append([a,b])
 
# マス目(初期値は「-1」)
Grid=[[-1]*(N+1) for i in range(N+1)]
 
# (1)スタート地点(1,1)に「0」を書き込む
Grid[1][1]=0
 
# dequeのインポート
from collections import deque
# キューを用意
que=deque()
# (2)キューにスタート地点(1,1)を追加
que.append([1,1])
 
# (5)キューが空でなければ(3)へ戻る
while 0<len(que):
    # (3)キューから座標を取り出し(今いる行、今いる列)、書かれている数字を確認
    # キューから座標を取り出し
    NowG,NowR=que.popleft()
    # 今いるマスの数字
    Num=Grid[NowG][NowR]
 
    # (4)今いるマスから進めるマスについてまだ数字が書き込まれていなければ「今いるマスの数字+1」を書き込み、キューへ追加する
    # dから行方向、列方向の増加量を取り出し
    # Gd,Rd：dの各要素を順に格納
    for Gd,Rd in d:
        # 1≤NowG+Gd≤N(今いるマスから行方向にGd進んだマスがマス目の範囲内)
        # かつ
        # 1≤NowR+Rd≤N(今いるマスから列方向にRd進んだマスがマス目の範囲内)
        if 1<=NowG+Gd<=N and 1<=NowR+Rd<=N:
            # まだ数字が書き込まれていなければ(-1ならば)
            if Grid[NowG+Gd][NowR+Rd]==-1:
                # 「今いるマスの数字+1」を書き込む
                Grid[NowG+Gd][NowR+Rd]=Num+1
                # キューに追加
                que.append([NowG+Gd,NowR+Rd])
 
# G=1~N
for G in range(1,N+1):
    # G行目の1列目以降を出力(「*」をつけるとカッコなしで出力できる)
    print(*Grid[G][1:])

ABC273 A

# 入力の受け取り
N=int(input())
 
# mathライブラリのインポート
import math
 
# N!を出力
print(math.factorial(N))

# 入力の受け取り
N=int(input())
 
# 関数fを定義
def f(k):
    # k=0ならば
    if k==0:
        # 1を返す
        return 1
    # そうでなければ
    else:
        # k*f(k-1)を返す
        return k*f(k-1)
 
# f(N)を計算して返す
print(f(N))

ABC273 B

# 入力の受け取り(文字列として)
X,K=map(str,input().split())
K=int(K)
 
# N=Xの桁数
N=len(X)
 
# (Xの桁数)<Kならば
if N<K:
    # 0を出力
    print(0)
    # 終了
    exit()
 
# Xを1文字ずつリストへ展開
X=list(X)
 
# i=0~(N-1)
for i in range(N):
    # 文字列→整数へ変換
    X[i]=int(X[i])
 
# 桁数が増えたときのために先頭に[0]を追加する
X=[0]+X
 
# i=N~(N-K+1) -1ずつ
for i in range(N,N-K,-1):
    # 5≤X[i]ならば
    if 5<=X[i]:
        # 次の桁へプラス1
        X[i-1]+=1
    # X[i]を0にする
    X[i]=0
 
# 繰り上がりの計算
# i=N~1 -1ずつ
for i in range(N,0,-1):
    # 10≤X[i]ならば
    if 10<=X[i]:
        # 次の桁へプラス1
        X[i-1]+=1
        # X[i]からマイナス10
        X[i]-=10  
 
# 答え
ans=""
 
# i=0~N
for i in range(N+1):
    # 整数→文字列へ変換してansへくっつける
    ans+=str(X[i])
 
# 整数へ変換(先頭に0があれば消す)
ans=int(ans)
 
# 答えの出力
print(ans)

# 入力の受け取り
X,K=map(int,input().split())
 
# 四捨五入する関数
def Round(X,i):
    # |X-Y|が最小になる候補の数のうち小さい方
    Yf=(X//10**(i+1))*10**(i+1)
    # |X-Y|が最小になる候補の数のうち大きい方
    Yc=(X//10**(i+1))*10**(i+1)+10**(i+1)
 
    # |Yf-X|<|Yc-x|ならば
    if abs(Yf-X)<abs(Yc-X):
        # Yfを返す
        return Yf
    # そうでなければ
    else:
        # Ycを返す
        return Yc
 
# i=0~(K-1)
for i in range(K):
    # 四捨五入
    X=Round(X, i)
 
# Xを出力
print(X)

ABC273 C

# 入力の受け取り
N=int(input())
A=list(map(int,input().split()))
 
# Aを小さい順にソート
A.sort()
# Aの要素をセットへ入れ直す(重複除去)
As=set(A)
 
# 各種類数ごとのカウント
Count=[0]*N
 
# i=0~(N-1)
for i in range(N):
    # A[i]がAsに含まれていれば
    if A[i] in As:
        # Asから除去
        As.remove(A[i])
    # A[i]より大きい要素は(len(As))種類ある
    # カウントする
    Count[len(As)]+=1
   
# i=0~(N-1)
for i in range(N):
    # 答えの出力
    print(Count[i])

ABC273 D

# pypyで提出
 
# 入力の受け取り
H,W,rs,cs=map(int,input().split())
N=int(input())
 
# defaultdictのインポート
from collections import defaultdict
 
# 各行ごとの壁マスの列を記録
# 初期値は空のリスト
KabeDR=defaultdict(list)
# 各列ごとの壁マスの行を記録
KabeDC=defaultdict(list)
 
# [行,列]の順に記録するリスト
RC=[]
# [列,行]の順に記録するリスト
CR=[]
 
# N回
for i in range(N):
    # 入力の受け取り
    r,c=map(int,input().split())
    # 記録
    RC.append([r,c])
    CR.append([c,r])
 
# 行の小さい順にソート
RC.sort()
# 列の小さい順にソート
CR.sort()
 
# r,c：RCの各要素を順に格納
for r,c in RC:
    # 列cのr行目に壁がある
    # ソートしているから行番号の小さい順に記録ができる
    KabeDC[c].append(r)
 
# 行も同様
for c,r in CR:
    KabeDR[r].append(c)
 
# 右方向への二分探索
# 今いるマスから右方向で最も近い壁マスの列番号を返す
def NibutanR(NowR,NowC):
    # 長さが0⇔今いる行に壁マスがない場合
    if len(KabeDR[NowR])==0:
        # 一番近い壁の列番号は(W+1)
        return W+1
    # 長さが1以上　かつ　最も大きい(右側にある)壁マスの列番号<今いるマスの列番号
    elif KabeDR[NowR][-1]<NowC:
        # 一番近い壁の列番号は(W+1)
        return W+1
    # 長さが1以上　かつ　今いるマスの列番号<最も小さい(左側にある)壁マスの列番号
    elif NowC<KabeDR[NowR][0]:
        # 一番近い壁の列番号はKabeDR[NowR][0](最も小さい壁マスの列番号)
        return KabeDR[NowR][0]
   
    # 探索範囲の決定
    # 左
    l=0
    # 右
    r=len(KabeDR[NowR])-1
 
    # 1<(右-左)である間
    while 1<r-l:
        # 中央
        c=(l+r)//2
 
        # 中央の壁マスの列番号<今いるマスの列番号
        if KabeDR[NowR][c]<NowC:
            # 左=中央と更新
            l=c
        # そうでない場合(今いるマスの列番号<中央の壁マスの列番号)
        else:
            # 右=中央と更新
            r=c
   
    # 今いるマスから右方向で最も近い壁マスの列番号を返す
    return KabeDR[NowR][r]
 
# 左方向への二分探索
# 今いるマスから左方向で最も近い壁マスの列番号を返す
def NibutanL(NowR,NowC):
    if len(KabeDR[NowR])==0:
        # 一番近い壁の列番号は0
        return 0
    # 長さが1以上　かつ　今いるマスの列番号<最も小さい(左側にある)壁マスの列番号
    elif NowC<KabeDR[NowR][0]:
        # 一番近い壁の列番号は0
        return 0
    # 長さが1以上　かつ　最も大きい(右側にある)壁マスの列番号<今いるマスの列番号
    elif KabeDR[NowR][-1]<NowC:
        # 一番近い壁の列番号はKabeDR[NowR][-1](最も大きい壁マスの列番号)
        return KabeDR[NowR][-1]
   
    # 探索範囲の決定
    # 左
    l=0
    # 右
    r=len(KabeDR[NowR])-1
 
    # 1<(右-左)である間
    while 1<r-l:
        # 中央
        c=(l+r)//2
 
        # 中央の壁マスの列番号<今いるマスの列番号
        if KabeDR[NowR][c]<NowC:
            # 左=中央と更新
            l=c
        # そうでない場合(今いるマスの列番号<中央の壁マスの列番号)
        else:
            # 右=中央と更新
            r=c
   
    # 今いるマスから左方向で最も近い壁マスの列番号を返す
    return KabeDR[NowR][l]
 
# 下方向への二分探索
# 今いるマスから右方向で最も近い壁マスの行番号を返す
def NibutanD(NowR,NowC):
    # 長さが0⇔今いる行に壁マスがない場合
    if len(KabeDC[NowC])==0:
        # 一番近い壁の行番号は(H+1)
        return H+1
    # 長さが1以上　かつ　最も大きい(下側にある)壁マスの行番号<今いる行
    elif KabeDC[NowC][-1]<NowR:
        # 一番近い壁の行番号は(H+1)
        return H+1
    # 長さが1以上　かつ　今いるマスの行番号<最も小さい(上側にある)壁マスの行番号
    elif NowR<KabeDC[NowC][0]:
        # 一番近い壁の列番号はKabeDC[NowC][0](最も小さい壁マスの行番号)
        return KabeDC[NowC][0]    
   
    # 探索範囲の決定
    # 左
    l=0
    # 右
    r=len(KabeDC[NowC])-1
 
    # 1<(右-左)である間
    while 1<r-l:
        # 中央
        c=(l+r)//2
 
        # 中央の壁マスの行番号<今いるマスの行番号
        if KabeDC[NowC][c]<NowR:
            # 左=中央と更新
            l=c
        # そうでない場合(今いるマスの行番号<中央の壁マスの行番号)
        else:
            # 右=中央と更新
            r=c
   
    # 今いるマスから右方向で最も近い壁マスの行番号を返す
    return KabeDC[NowC][r]
 
# 上方向への二分探索
# 今いるマスから上方向で最も近い壁マスの行番号を返す
def NibutanU(NowR,NowC):
    # 長さが0⇔今いる行に壁マスがない場合
    if len(KabeDC[NowC])==0:
        # 一番近い壁の行番号は0
        return 0
    # 長さが1以上　かつ　今いるマスの行番号<最も小さい(上側にある)壁マスの行番号
    elif NowR<KabeDC[NowC][0]:
        # 一番近い壁の行番号は0
        return 0
    # 長さが1以上　かつ　最も大きい(下側にある)壁マスの行番号<今いるマスの行番号
    elif KabeDC[NowC][-1]<NowR:
        # 一番近い壁の行番号はKabeDC[NowC][-1](最も大きい壁マスの行番号)
        return KabeDC[NowC][-1]
 
    # 探索範囲の決定
    # 左
    l=0
    # 右
    r=len(KabeDC[NowC])-1
 
    # 1<(右-左)である間
    while 1<r-l:
        # 中央
        c=(l+r)//2
 
        # 中央の壁マスの行番号<今いるマスの行番号
        if KabeDC[NowC][c]<NowR:
            # 左=中央と更新
            l=c
        # そうでない場合(今いるマスの行番号<中央の壁マスの行番号)
        else:
            # 右=中央と更新
            r=c
   
    # 今いるマスから上方向で最も近い壁マスの行番号を返す
    return KabeDC[NowC][l]
 
# 今いる行、列
NowR,NowC=rs,cs
 
# 入力の受け取り
Q=int(input())
 
# Q回
for i in range(Q):
    # 入力の受け取り
    d,l=map(str,input().split())
    # 整数へ変換
    l=int(l)
 
    # 右へ進む場合
    if d=="R":
        # 今いるマスから右方向で最も近い壁マスの列番号
        KabeC=NibutanR(NowR,NowC)
        # l右へ進んだ時の列番号<壁マスの列番号なら
        if NowC+l<KabeC:
            # 進む
            NowC+=l
        # そうでなければ
        else:
            # 壁マスの手前まで進む
            NowC=KabeC-1
   
    # 左へ進む場合
    elif d=="L":
        # 今いるマスから左方向で最も近い壁マスの列番号
        KabeC=NibutanL(NowR,NowC)
        # 壁マスの列番号<l左へ進んだ時の列番号なら
        if KabeC<NowC-l:
            # 進む
            NowC-=l
        # そうでなければ
        else:
            # 壁マスの手前まで進む
            NowC=KabeC+1
 
    # 下方向へ進む場合
    elif d=="D":
        # 今いるマスから下方向で最も近い壁マスの行番号
        KabeR=NibutanD(NowR,NowC)
        # l下へ進んだ時の行番号<壁マスの行番号なら
        if NowR+l<KabeR:
            # 進む
            NowR+=l
        # そうでなければ
        else:
            # 壁マスの手前まで進む
            NowR=KabeR-1
 
    # 上方向へ進む場合
    elif d=="U":
        # 今いるマスから上方向で最も近い壁マスの行番号
        KabeR=NibutanU(NowR,NowC)
        # 壁マスの行番号<l上へ進んだ時の行番号なら
        if KabeR<NowR-l:
            # 進む
            NowR-=l
        # そうでなければ
        else:
            # 壁マスの手前まで進む
            NowR=KabeR+1
 
    # 今いるマスを出力
    print(NowR,NowC)

# 入力の受け取り
H,W,NowR,NowC=map(int,input().split())
N=int(input())
 
# defaultdictのインポート
from collections import defaultdict
 
# 各行ごとの壁マスの列を記録
# 初期値は空のリスト
KabeDR=defaultdict(list)
# 各列ごとの壁マスの行を記録
KabeDC=defaultdict(list)
 
# 壁マスの情報記録
RC=[]
 
# N回
for i in range(N):
    # 入力の受け取り
    r,c=map(int,input().split())
    # 記録
    RC.append([r,c])
 
# 行の小さい順にソート
RC.sort()
 
# 各列ごとの壁マスの行番号を記録
for r,c in RC:KabeDC[c].append(r)
 
# 1番目の要素(列番号)の小さい順にソート
RC.sort(key=lambda x:x[1])
 
# 各行ごとの壁マスの列番号を記録
for r,c in RC:KabeDR[r].append(c)
 
# bisectのインポート
from bisect import bisect_left
 
# 入力の受け取り
Q=int(input())
 
# Q回
for i in range(Q):
    # 入力の受け取り
    d,l=map(str,input().split())
    # 整数へ変換
    l=int(l)
 
    # KabeCL=今いるマスから左方向で最も近い壁マスの列番号
    # KabeCR=今いるマスから右方向で最も近い壁マスの列番号
    # 今いる行に壁マスがない場合
    if len(KabeDR[NowR])==0:
        KabeCL=0
        KabeCR=W+1
    # ある場合
    else:
        # 二分探索でインデックス番号を確認
        indx=bisect_left(KabeDR[NowR],NowC)
 
        # インデックス番号が0
        # ⇔今いるマスの左に壁マスはない
        if indx==0:
            KabeCL=0
            KabeCR=KabeDR[NowR][0]
        # インデックス番号が(KabeDR[NowR])の長さと同じ
        # ⇔今いるマスの右に壁マスはない
        elif indx==len(KabeDR[NowR]):
            KabeCL=KabeDR[NowR][-1]
            KabeCR=W+1
        # それ以外
        else:
            KabeCL=KabeDR[NowR][indx-1]
            KabeCR=KabeDR[NowR][indx]
 
    # KabeRU=今いるマスから上方向で最も近い壁マスの列番号
    # KabeRD=今いるマスから下方向で最も近い壁マスの列番号
    # 今いる列に壁マスがない場合
    if len(KabeDC[NowC])==0:
        KabeRU=0
        KabeRD=H+1
    # ある場合
    else:
        # 二分探索でインデックス番号を確認
        indx=bisect_left(KabeDC[NowC],NowR)
       
        # インデックス番号が0
        # ⇔今いるマスの上に壁マスはない
        if indx==0:
            KabeRU=0
            KabeRD=KabeDC[NowC][0]
        # インデックス番号が(KabeDR[NowR])の長さと同じ
        # ⇔今いるマスの下に壁マスはない
        elif indx==len(KabeDC[NowC]):
            KabeRU=KabeDC[NowC][-1]
            KabeRD=H+1
        # それ以外
        else:
            KabeRU=KabeDC[NowC][indx-1]
            KabeRD=KabeDC[NowC][indx]
 
    # 右へ進む場合
    if d=="R":
        # l進んで壁にぶつかるか、確認して進む
        if NowC+l<KabeCR:NowC+=l
        else:NowC=KabeCR-1
   
    # 左へ進む場合
    if d=="L":
        if KabeCL<NowC-l:NowC-=l
        else:NowC=KabeCL+1
 
    # 下へ進む場合
    if d=="D":
        if NowR+l<KabeRD:NowR+=l
        else:NowR=KabeRD-1
   
    # 上へ進む場合
    if d=="U":
        if KabeRU<NowR-l:NowR-=l
        else:NowR=KabeRU+1
   
    # 今いるマスを出力
    print(NowR,NowC)

ABC274 A

# 入力の受け取り
A,B=map(int, input().split())
 
# (B/A)を少数第4位を四捨五入して3桁まで出力
print(f"{B/A:.3f}")

# 入力の受け取り
A,B=map(int, input().split())
 
# A=Bは例外として処理
if A==B:
    # 「1.000」を出力
    print("1.000")
# そうでなければ
else:
    # B*10000//Aを計算
    X=10000*B//A
    # 5を足す
    X+=5
    # 10で割った商を取る
    X//=10
    # 文字列へ変換
    X=str(X)
    # 3桁で0埋め
    X=X.zfill(3)
    # 答えの出力
    print("0."+X)

ABC274 B

# 入力の受け取り
H,W=map(int,input().split())
 
# 要素を記録するリスト
Grid=[]
 
# H回
for i in range(H):
    # 文字列として受け取り
    Ci=input()
    # 1文字ずつリストへ展開
    Ci=list(Ci)
    # 記録
    Grid.append(Ci)
 
# 答えの記録
ans=[]
 
# w=0~(W-1)
for w in range(W):
    # 「#」の個数
    count=0
 
    # h=0~(H-1)
    for h in range(H):
        # Grid[h][w]=「#」ならば
        if Grid[h][w]=="#":
            # カウント
            count+=1
 
    # 答えの記録
    ans.append(count)
 
# 答えの出力(「*」をつけると[]なしで出力できる)
print(*ans)

ABC274 C

# 入力の受け取り
N=int(input())
# 先頭をてきとうな数字(=0)で埋める
A=[0]+list(map(int,input().split()))
 
# 答え
ans=[0]*(2*N+2)
 
# i=1~N
for i in range(1,N+1):
    # (親の代+1)を記録する
    ans[2*i]=ans[A[i]]+1
    ans[2*i+1]=ans[A[i]]+1
 
# i=1~(2N+1)
for i in range(1,2*N+2):
    # 答えの出力
    print(ans[i])

ABC274 D

# 入力の受け取り
N,x,y=map(int,input().split())
# 先頭A[0]を適当な数字(=0)で埋めておく
A=[0]+list(map(int,input().split()))
 
# 到達可能なx座標のセット
Sx=set()
# 到達可能なy座標のセット
Sy=set()
 
# p2の時点でx座標はA1
Sx.add(A[1])
# y座標は0
Sy.add(0)
 
# i=2~N
for i in range(2,N+1):
    # 偶数番目(y座標方向への移動)
    if i%2==0:
        # 新しい到達先のy座標
        NewSy=set()
 
        # yi：Syの要素を順に代入
        for yi in Sy:
            # 新しい到達先を記録
            NewSy.add(yi-A[i])
            NewSy.add(yi+A[i])
 
        # Syを更新
        Sy=NewSy
 
    # 奇数番目(x座標方向への移動)
    else:
        # 新しい到達先のx座標
        NewSx=set()
 
        # xi：Sxの要素を順に代入
        for xi in Sx:
            # 新しい到達先を記録
            NewSx.add(xi-A[i])
            NewSx.add(xi+A[i])
       
        # Sxを更新
        Sx=NewSx
 
# xがSxにある かつ yがSyにある
if x in Sx and y in Sy:
    # 「Yes」を出力
    print("Yes")
# そうでなければ
else:
    # 「No」を出力
    print("No")

ABC275 A

# 入力の受け取り
N=int(input())
H=list(map(int,input().split()))
 
# Hの中で最も大きい要素
Hmax=max(H)
 
# (Hmaxのインデックス番号+1)を出力
print(H.index(max(H))+1)

ABC275 B

# 入力の受け取り
A,B,C,D,E,F=map(int,input().split())
 
# 計算して出力
print((A*B*C-D*E*F)%998244353)

ABC275 C

# 座標の情報記録
S=[]
 
# 9回
for i in range(9):
    # 入力の受け取り
    Si=input()
    # 1文字ずつリストへ展開(なくてもOK)
    Si=list(Si)
    # 記録
    S.append(Si)
 
# 正方形になっている組のカウント
count=0
 
# Aの行番号：Ar=0~8
for Ar in range(9):
    # Aの列番号：Ac=0~8
    for Ac in range(9):
        # Bの行番号：Br=Ar~8
        for Br in range(Ar,9):
            # Bの列番号：Br=(Ac+1)~8
            for Bc in range(Ac+1,9):
                # (Ar,Ac),(Br,Bc)が「#」ならば
                if S[Ar][Ac]=="#" and S[Br][Bc]=="#":
                    # Bの行番号+(A→Bの列方向の増加量)
                    Cr=Br+(Bc-Ac)
                    # Bの列番号-(A→Bの行方向の増加量)
                    Cc=Bc-(Br-Ar)
                    # Cの行番号-(C→Bの列方向の増加量)
                    Dr=Cr-(Bc-Cc)
                    # Cの列番号-(B→Cの行方向の増加量)
                    Dc=Cc-(Cr-Br)
 
                    # 全て座標の範囲内に収まっていれば
                    if 0<=Cr<=8 and 0<=Dr<=8 and 0<=Cc<=8 and 0<=Dc<=8:
                        # (Cr,Cc),(Dr,Dc)が「#」ならば
                        if S[Cr][Cc]=="#" and S[Dr][Dc]=="#":
                            # カウント
                            count+=1
 
# 答えの出力
print(count)

ABC275 D

# 入力の受け取り
N=int(input())
 
# メモ化再帰
from functools import lru_cache
@lru_cache()
# fを定義
def f(k):
    # k=0ならば
    if k==0:
        # 1を返す
        return 1
    # そうでなければ
    else:
        # 計算
        return f(k//2)+f(k//3)
 
# 計算して出力
print(f(N))

ARC140 A

# 入力の受け取り
N,K=map(int,input().split())
S=input()
 
from collections import defaultdict
 
# x文字ずつ区切る
# x=1~N
for x in range(1,N+1):
    # xがNの約数である場合⇔Nをxで割った余りが0
    if N%x==0:
        # 必要な操作回数
        Ope=0
        # 文字確認のスタート地点：s=0~x
        for s in range(x):
            # 文字の出現回数をカウント
            Count=defaultdict(int)
            # 最も多い文字の個数
            Cmax=0
            # k=s,s+x,s+2x,...
            for k in range(s,N,x):
                # S[k]をカウント
                Count[S[k]]+=1
                # 文字の最大個数を更新
                Cmax=max(Count[S[k]],Cmax)
           
            # 最大個数の文字に合わせる
            # 操作回数に(N//x-(文字の最大個数))をプラス
            Ope+=N//x-Cmax
       
        # 操作回数≤Kならば
        if Ope<=K:
            # xを出力
            print(x)
            # 終了
            exit()

ARC140 B

# 入力の受け取り
N=int(input())
S=input()
 
# "A...ARC...C"の塊を記録するリスト
A=[]
 
# "A...ARC...C"の塊を数える
# 初期値
i=0
# i+2<Nの間
while i+2<N:
    # "ARC"が見つかったら
    if S[i:i+3]=="ARC":
        # k個前とk個後を確認する
        k=0
 
        # 0≤(i-k) かつ i+2+k<N である間
        while 0<=i-k and i+2+k<N:
            # k個前が"A" かつ k個後が"C"
            if S[i-k]=="A" and S[i+2+k]=="C":
                # 次のkへ
                k+=1
            # そうでない場合
            else:
                # 終了
                break
        # Aに記録
        A.append(k)
        # iを進める
        i=i+1+k
    # 次のiへ
    i+=1
   
# heapqのインポート
import heapq
 
# Aの最大値取り出し用
Amax=[]
# Aの最小値取り出し用
Amin=[]
 
# Aに残っている個数の確認用(大きめに取っている)
Count=[0]*(3*10**5)
 
# x：Aの各要素について
for x in A:
    # (-x)をAmaxへ入れる
    heapq.heappush(Amax,-x)
    # xをAminへ入れる
    heapq.heappush(Amin,x)
    # 個数をカウント
    Count[x]+=1
 
# 答え(操作回数)
ans=0
 
# Amin,Amaxが空でない間
while 0<len(Amin) and 0<len(Amax):
    # 奇数回目の操作
    if (ans+1)%2==1:
        # 最大値の取り出し
        x=heapq.heappop(Amax)
        # (-1)倍する
        x*=-1
 
        # Aminが空でない かつ xがAに存在しない(Countが0)
        while 0<len(Amax) and Count[x]==0:
            # 最大値の取り出し
            x=heapq.heappop(Amax)
            # (-1)倍する
            x*=-1
       
        # xがAに存在しない
        if Count[x]==0:
            # 終了
            break
       
        # xが1個減る
        Count[x]-=1
        # (x-1)が1個増える
        Count[x-1]+=1
        # 操作回数が増える
        ans+=1
 
        # (x-1)が0でなければ
        if x-1!=0:
            # (x-1)をAmax,Aminへ戻す
            heapq.heappush(Amax,-(x-1))
            heapq.heappush(Amin,x-1)
 
    else:
        # 最小値の取り出し
        x=heapq.heappop(Amin)
 
        # xがAにまだあるか確認
        # Aminが空でない かつ xがAに存在しない(Countが0)
        while 0<len(Amin) and Count[x]==0:
            # 最小値の取り出し
            x=heapq.heappop(Amin)
 
        # xがAに存在しない
        if Count[x]==0:
            # 終了
            break
           
        # 個数が1個減る
        Count[x]-=1
        # 操作回数が増える
        ans+=1
 
# 答えの出力
print(ans)

ARC141 A

# 入力の受け取り
T=int(input())
 
# 切り上げ計算のためインポート
from math import ceil
 
# 二分探索：k個連結する場合
def Nibutan(k):
    # (1)左=区間の最小、右=区間の最大　とする
    # 左
    l=1
    # 右(9を(Nの桁数)/kの切り上げ)個連結した数+1
    r=int("9"*(ceil(Nd/k)))+1
 
    # (4)1<(右-左)となっている間(2)~(4)を繰り返す
    while 1<r-l:
        # (2)中央=(左+右)//2が条件を満たすか確認
        c=(l+r)//2
        # cをk個連結した数を整数へ変換
        Num=int(str(c)*k)
 
        # (3)(2)の結果より左または右を更新する
        # Num≤Nならば
        if Num<=N:
            # 左=中央と更新
            l=c
        # そうでなければ(N<Num)
        else:
            # 右=中央と更新
            r=c
 
    # 左をk個連結した数を返す
    return int(str(l)*k)
 
# T回
for i in range(T):
    # 入力の受け取り
    N=input()
    # 桁数の確認
    Nd=len(N)
    # 整数へ変換
    N=int(N)
 
    # 答え
    ans=0
 
    # k=2~18
    for k in range(2,19):
        # 1をk個連結した数≤Nならば
        if int("1"*k)<=N:
            # k個連結した数の最大で答えを更新
            ans=max(ans,Nibutan(k))
 
    # 答えの出力
    print(ans)

ARC142 A

# 入力の受け取り
N,K=map(int,input().split())
 
# f(x)の計算
def f(x):
    # 値
    result=x
    # 文字列へ変換
    x=str(x)
    # 反転
    x=x[::-1]
    # 整数へ戻す(末尾にあった0が消える)
    x=int(x)
    # 最小値を取る
    result=min(result,x)
 
    # 文字列へ変換
    x=str(x)
    # 反転
    x=x[::-1]
    # 整数へ戻す
    x=int(x)
    # 最小値を取る
    result=min(result,x)
   
    # 値を返す
    return result
 
# f(x)=Kとなるxを格納
ans=set()
 
# f(x)=Kとなるxの候補
x=K
# xの末尾に0を0個以上並べた数
while x<=N:
    # f(x)=Kならば
    if f(x)==K:
        # 答えに追加
        ans.add(x)
    # xを10倍
    x*=10
 
# 同様の操作を反転して行う
x=K
# 文字列へ変換
x=str(x)
# 反転
x=x[::-1]
# 整数へ戻す
x=int(x)
while x<=N:
    if f(x)==K:
        ans.add(x)
    x*=10
 
# 答えの種類数を出力
print(len(ans))

ARC142 B

# 入力の受け取り
N=int(input())
 
# マス目
Grid=[[0]*N for i in range(N)]
 
# 埋める数字
Num=1
# G=0~(N-1) 2毎に増える
for G in range(0,N,2):
    # R=0~(N^1)
    for R in range(N):
        # マス目を埋める
        Grid[G][R]=Num
        # 次の数へ
        Num+=1
 
# G=1~(N-1) 2毎に増える
for G in range(1,N,2):
    # R=0~(N^1)
    for R in range(N):
        # マス目を埋める
        Grid[G][R]=Num
        # 次の数へ
        Num+=1
 
# G=0~(N^1)
for G in range(N):
    # 答えの出力(*をつけるとカッコなしで出力できる)
    print(*Grid[G])

ARC143 A

# 入力の受け取り(リストで受け取るとソートができる)
X=list(map(int,input().split()))
 
# ソート
X.sort()
# 変数を割り当て
A,B,C=X
 
# A+B<Cならば
if A+B<C:
    # 目標達成不可
    print(-1)
# そうでなければ
else:
    # C回
    print(C)

ARC144 A

# 入力の受け取り
N=int(input())
 
# Mを出力
print(2*N)
 
# Nが4で割り切れる場合
if N%4==0:
    # 4を(N//4)個並べる
    print((N//4)*"4")
# そうでない場合
else:
    # (N%4)を先頭に 4を(N//4)個並べる
    print(str(N%4)+(N//4)*"4")

ARC144 B

# 入力の受け取り
N,a,b=map(int,input().split())
A=list(map(int,input().split()))
 
# x/aの切り上げ
def Ceil(x,a):
    # 割り切れるなら
    if x%a==0:
        # 商を返す
        return x//a
    # 割り切れないなら
    else:
        # (商+1)を返す
        return x//a+1
 
# C≤min(A)が達成できるか判定する関数
def Judge(C):
    # +aの最低操作回数
    aCount=0
    # -bの許容操作回数
    bCount=0
 
    # x：Aの各要素について
    for x in A:
        # x<Cならば
        if x<C:
            # ((C-x)/aの切り上げ)回操作が必要
            aCount+=Ceil((C-x),a)
        # C≤xならば
        else:
            # ((x-C)//b)回まで操作が可能
            bCount+=(x-C)//b
 
    # (+aの操作回数)≤(-bの操作回数)ならば
    if aCount<=bCount:
        # Trueを返す(達成可能)
        return True
    # そうでないなら
    else:
        # Falseを返す(達成不可能)
        return False
 
# (1)左=区間の最小、右=区間の最大　とする
l=1
# 左はmax(A)でも良いがてきとうに大きめにしておくのが楽
r=10**9+10
 
# (4)1<(右-左)となっている間(2)~(4)を繰り返す
while 1<r-l:
    # (2)中央=(左+右)//2が条件を満たすか確認
    c=(l+r)//2
    # (3)(2)の結果より左または右を更新する
    # 達成可能
    if Judge(c)==True:
        # 左=中央
        l=c
    # 達成不可能
    else:
        # 右=中央
        r=c
 
# 左が答え
print(l)

ARC145 A

# 入力の受け取り
N=int(input())
S=input()
 
# S="BA"の場合
if S=="BA":
    # 「No」を出力
    print("No")
# 先頭が"B"の場合
elif S[0]=="B":
    # 「Yes」を出力
    print("Yes")
# 先頭が"A"かつ末尾も"A"の場合
elif S[0]=="A" and S[-1]=="A":
    # 「Yes」を出力
    print("Yes")
# 先頭が"A"かつ末尾は"B"の場合
elif S[0]=="A" and S[-1]=="B":
    # 「No」を出力
    print("No")

ARC145 B

# 入力の受け取り
N,A,B=map(int,input().split())
 
# N<Aの場合
if N<A:
    # Aliceは全敗
    print(0)
# A≤N かつ A≤Bの場合
elif A<=B:
    # A≤n≤NでAliceは全勝
    print(N-A+1)
# A≤N かつ B<Aの場合
else:
    # Aliceの勝てるnの個数
    print((N//A-1)*B+min(N%A+1,B))

ARC146 A

# 入力の受け取り
N=int(input())
A=list(map(int,input().split()))
 
# 大きい順に並び替え
A.sort(reverse=True)
 
# 大きい順に3枚取る
X=str(A[0])
Y=str(A[1])
Z=str(A[2])
 
# 答え
ans=0
 
# 並び替えてもっとも大きいものを探す
ans=max(ans,int(X+Y+Z))
ans=max(ans,int(X+Z+Y))
ans=max(ans,int(Y+X+Z))
ans=max(ans,int(Y+Z+X))
ans=max(ans,int(Z+X+Y))
ans=max(ans,int(Z+Y+X))
 
# 答えの出力
print(ans)

ARC147 A

# 入力の受け取り
N=int(input())
A=list(map(int,input().split()))
 
# ソートする
A.sort()
 
# dequeのインポート
from collections import deque
# Aをdequeにする
A=deque(A)
 
# 答え
ans=0
 
# Aの長さが1以上である限り
while 1<len(A):
    # 答えにプラス1
    ans+=1
    # 最大値(右端)を取り出す
    Ai=A.pop()
    # 最小値(左端)を確認
    Aj=A[0]
 
    # Ai%Aj≠0ならば
    if Ai%Aj!=0:
        # Ai%Ajを左端に追加
        A.appendleft(Ai%Aj)
 
# 答えの出力
print(ans)

ARC147 B

# 入力の受け取り
N=int(input())
# Pの0番目を埋めておく
P=[0]+list(map(int,input().split()))
 
# ソート済みのP
PS=sorted(P)
 
# 既にソート済みなら
if P==PS:
    # 0を出力
    print(0)
    # 終了
    exit()
 
# 答え
ans=[]
 
# OK：Pの要素全てについて添字と偶奇が一致したらTrue
OK=False
# Pに添字と偶奇が一致していない要素がある限り
while OK==False:
    # i=1~N
    for i in range(1,N+1):
        # 添字と偶奇が一致していなければ
        if i%2!=P[i]%2:
            # (i+1)≤Nである限り(インデックスの範囲内である限り)
            while i+1<=N:
                # 隣の要素も添字と偶奇が一致していなければ
                if (i+1)%2!=P[i+1]%2:
                    # 入れ替え
                    P[i],P[i+1]=P[i+1],P[i]
                    # 答えの記録
                    ans.append(["A",i])
                    # 次の要素へ
                    break
                # そうでなければ
                else:
                    # (i+2)≤Nである限り(インデックスの範囲内である限り)
                    if i+2<=N:
                        # 入れ替えてPiを移動
                        P[i],P[i+2]=P[i+2],P[i]
                        # 答えの記録
                        ans.append(["B",i])
                    # 次のiへ
                    i+=2
 
    # Pに添字と偶奇が一致していない要素があるか確認
    # OKをTrueにする
    OK=True
    # i=1~N
    for i in range(1,N+1):
        # 添字と偶奇が一致していない要素があれば
        if i%2!=P[i]%2:
            # Falseに変更
            OK=False
            # forを抜ける
            break
 
# 添字と偶奇が一致したら
 
# OK：Pがソート完了したらTrue
OK=False
# Pがソート完了するまで
while OK==False:
    # i=1~(N-2)
    for i in range(1,N-1):
        # 大小が逆なら
        if P[i+2]<P[i]:
            # 入れ替え
            P[i],P[i+2]=P[i+2],P[i]
            # 答えの記録
            ans.append(["B",i])
 
    # ソート済みの数列と一致したら
    if P==PS:
        # ソート完了
        OK=True
 
# 答えの出力
# 長さの出力
print(len(ans))
# x：ansの各要素
for x in ans:
    # xを出力(「*」をつけると[]なしで出力できる)
    print(*x)

ARC148 A

# 入力の受け取り
N=int(input())
A=list(map(int,input().split()))
 
# Aをソート
A.sort()
 
# gcdのインポート
from math import gcd
 
# 最大公約数 初期値=0
g=0
# i=1~(N-1)
for i in range(1,N):
    # 最大公約数を計算
    g=gcd(g,A[i]-A[i-1])
 
# 最大公約数が1なら
if g==1:
    # 2が答え(M=2)
    print(2)
# そうでなければ
else:
    # 1が答え
    print(1)

ARC148 B

# 入力の受け取り
N=int(input())
S=input()
 
# "p"がSにない場合
if "p" not in S:
    # Sを出力
    print(S)
    # 終了
    exit()
 
# 先頭から一番最初にある"p"のインデックス番号
L=S.index("p")
 
# 操作
def f(T):
    # 反転
    T=T[::-1]
    # 結果
    result=""
    # x：Tの各要素について
    for x in T:
        # "d"ならば
        if x=="d":
            # "p"を追加
            result+="p"
        # そうでなければ("p"ならば)
        else:
            # "d"を追加
            result+="d"
    # 結果を返す
    return result        
 
# 答え
ans=S
 
# R=(L+1)~N
for R in range(L+1,N+1):
    # 操作後のものと辞書順の小さい方を採用
    ans=min(ans,S[:L]+f(S[L:R])+S[R:])
# 答えの出力
print(ans)

ARC149 A

# 入力の受け取り
N,M=map(int,input().split())
 
# 答え
ans=""
 
# i=1~9
for i in range(1,10):
    # 余り
    amari=0
 
    # k=1~N
    for k in range(1,N+1):
        # 余りを10倍してプラスi
        amari=(amari*10+i)%M
        # 余りが0なら
        if amari==0:
            # ansの桁数≤k ならば
            if len(ans)<=k:
                # 答えをiをk個並べたものに更新
                ans=str(i)*k
 
# ansが更新されていなければ
if len(ans)==0:
    # 「-1」を出力
    print(-1)
# そうでなければ
else:
    # 答えを出力
    print(ans)

ARC149 B

# bisectのインポート
import bisect
 
# リストXについてLISを求める
def LIS(X):
    # Tableを用意
    Table=[X[0]]
 
    # x：Xの各要素について
    for x in X:
        # Tableの最大値(右端)<x ならば
        if Table[-1]<x:
            # Tableの右端にxを追加
            Table.append(x)
        # そうでなければ
        else:
            # Tableの要素のうち、x以上で最も小さい要素をxに変える
            Table[bisect.bisect_left(Table,x)]=x
    # Tableの長さを返す
    return len(Table)
 
# 入力の受け取り
N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
 
# A,Bを格納するリスト
AB=[]
# i=0~(N-1)
for i in range(N):
    # ABへ追加
    AB.append([A[i],B[i]])
# ABをソート(Aを昇順にする)
AB.sort()
 
# Bを戻す
B=[]
# i=0~(N-1)
for i in range(N):
    # ABからBの要素だけを取り出し
    B.append(AB[i][1])
 
# LIS(A)(=N)+LIS(B)を出力
print(N+LIS(B))

ARC150 A

# 入力の受け取り
T=int(input())
 
# T回
for t in range(T):
    # 入力の受け取り
    N,K=map(int,input().split())
    S=input()
 
    # Sに含まれる1の数
    C1=S.count("1")
 
    # S[0]~S[K-1]に含まれる1の数
    tmpC1=S[:K].count("1")
    # S[0]~S[K-1]に含まれる0の数
    tmpC0=S[:K].count("0")
 
    # 条件を満たす区間の個数
    ansCount=0
 
    # i=0~(N-K)
    for i in range(N-K+1):
        # ・Sのi文字目~Sの(i+K-1)文字目に0はない(1か?)
        # ・Sのi文字目~Sの(i+K-1)文字目にSに含まれる1が全て入っている
        if tmpC0==0 and tmpC1==C1:
            # S[i]~S[i+K-1]を全て1にすることで条件を満たす
            # 答えにカウント
            ansCount+=1
 
        # i+K<Nならば(インデックス内ならば)
        if i+K<N:
            # S[i]=区間の左端(消える部分)が1ならば
            if S[i]=="1":
                # 1の個数をマイナス1
                tmpC1-=1
            # S[i]=区間の左端(消える部分)が0ならば
            elif S[i]=="0":
                # 0の個数をマイナス0
                tmpC0-=1
           
            # S[i+K]=区間の右端(増える部分)が1ならば
            if S[i+K]=="1":
                # 1の個数をマイナス1
                tmpC1+=1
            # S[i+K]=区間の右端(増える部分)が0ならば
            elif S[i+K]=="0":
                # 0の個数をマイナス0
                tmpC0+=1
 
    # 条件を満たす区間がちょうど1つ
    if ansCount==1:
        # 「Yes」を出力
        print("Yes")
    # そうでない(0か2以上)
    else:
        # 「No」を出力
        print("No")

ARC151 A

# 入力の受け取り
N=int(input())
S=input()
T=input()
 
# S[i]≠T[i]となっている箇所の個数
d=0
 
# i=0~(N-1)
for i in range(N):
    # S[i]≠T[i]ならば
    if S[i]!=T[i]:
        # カウント
        d+=1
 
# dが奇数ならば
if d%2==1:
    # -1を出力
    print(-1)
# dが偶数ならば
else:
    # 答え
    U=""
 
    # S[i]=U[i]にした箇所の個数
    SCount=0
    # T[i]=U[i]にした箇所の個数
    TCount=0
 
    # i=0~(N-1)
    for i in range(N):
        # S[i]=T[i]ならば
        if S[i]==T[i]:
            # U[i]=0とする
            U+="0"
       
        # そうでなければ
        else:
            # S[i]=0の場合
            if S[i]=="0":
                # S[i]=U[i]にした箇所の個数が(d/2)未満ならば
                if SCount<d//2:
                    # U[i]=0とする
                    U+="0"
                    # カウント
                    SCount+=1
                # そうでなければ(S[i]=U[i]とできない場合)
                else:
                    # U[i]=1とする
                    U+="1"
                    # カウント
                    TCount+=1
 
            # そうでなければ
            else:
                # T[i]=0の場合
                if T[i]=="0":
                    # T[i]=U[i]にした箇所の個数が(d/2)未満ならば
                    if TCount<d//2:
                        # U[i]=0とする
                        U+="0"
                        # カウント
                        TCount+=1
                    # そうでなければ(T[i]=U[i]とできない場合)
                    else:
                        # U[i]=1とする
                        U+="1"
                        # カウント
                        SCount+=1
       
    # 答えの出力
    print(U)

UnionFind

# UnionFind
class UnionFind:
    # UnionFind(N)：要素数Nで初期化。
    # 引数：N(要素数)　→　返り値：なし
    def __init__(self,N):
        # 要素数
        self.N=N
        # 根の番号　と　木の要素数
        # マイナスの場合:グループの要素数(自身が根)
        # プラスの場合:根の番号
        self.parent_size=[-1]*N
　 
    # leader(a)：aの根を返す
    # 引数：a　→　返り値：aの根
    def leader(self,a):
        # aが根ならa自身を返す
        if self.parent_size[a]<0: return a
        # aが根でないなら根に向かって木をたどる＋根の更新
        self.parent_size[a]=self.leader(self.parent_size[a])
        # 根を返す
        return self.parent_size[a]
　 
    # merge(a,b)：aとbを連結
    # 引数：a,b　→　返り値：なし
    def merge(self,a,b):
        # a,bの根をx,yへ
        x,y=self.leader(a),self.leader(b)
        # 根が同じなら終了
        if x == y: return
        # 木の要素数を比較　小さい方を大きい方につなげるため
        # x<yならばx,yを入れ替える(xを大きい方にしたい)
        if abs(self.parent_size[x])<abs(self.parent_size[y]):x,y=y,x
        # 要素数の更新：小さい方の要素数を大きい方の要素数に足す
        self.parent_size[x] += self.parent_size[y]
        # 要素数が小さい方の根を大きい方の根につなげる
        self.parent_size[y]=x
　 
    # same(a,b)：aとbの根が同じか確認
    # 引数：a,b　→　返り値：True(根が同じ)　False(根が違う)
    def same(self,a,b):
        # 根を比較し、同じならTrueを返す
        return self.leader(a) == self.leader(b)

FenwickTree

# FenwickTree
class FenwickTree:
    # 「FenwickTree(N)：要素数Nで初期化」
    # 引数：N　→　返り値：なし
    def __init__(self,N):
        self.N=N
        # F：長さNのリスト
        self.F=[0]*N
　
    # 「add(i,x)：i番目の要素にxを加算」
    # 引数：i,x　→　返り値：なし
    def add(self,i,x):
        # 1インデックスにするため1を加算
        i+=1
        # i≤Nの間
        while i<=self.N:
            # xを加算
            # iはプラス1されているのでF[i-1]に加算
            self.F[i-1]+=x
            # 次のi
            i+=i&-i
　
    # 「sum_r(r)：区間[0,r)の区間和を計算」
    # 引数：r　→　返り値：区間[0,r)の区間和
    def sum_r(self,r):
        # 合計
        s=0
        # 0<rの間
        while 0<r:
            # sに加算
            s+=self.F[r-1]
            # 次のr
            r-=r&-r
        # 合計を返す
        return s
　
    # 「sum(l,r)：区間[l,r]の区間和を計算」
    # 引数：l,r　→　返り値：区間[l,r]の区間和
    def sum(self,l,r):
        # 「区間[l,r]の区間和」=「区間[0,r+1)の区間和」-「区間[0,l)の区間和」
        return self.sum_r(r+1)-self.sum_r(l)
　
    # 「select(i)：i番目の要素を出力」
    # 引数：i　→　返り値：i番目の要素
    def select(self,i):
        # 区間[i,i]の区間和
        return self.sum(i,i)