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

ABC271～275,ARC140～151,UnionFind,FenwickTree
https://qiita.com/sano192/items/a2b11bd960ccffffa8ea

ABC251 A

# 入力の受け取り
S=input()
 
# 文字数が1の場合
if len(S)==1:
    # Sを6個くっつけて出力
    print(S*6)
# 文字数が2の場合
elif len(S)==2:
    # Sを3個くっつけて出力
    print(S*3)
# それ以外(文字数が3の場合)
else:
    # Sを2個くっつけて出力
    print(S*2)

ABC251 B

# 入力の受け取り
N,W=map(int,input().split())
A=list(map(int,input().split()))
 
# 重さの種類を記録していくセット
Weight=set()
 
# おもりを1個選ぶ場合
# i=0~(N^1)
for i in range(N):
    # 重さがW以下ならば
    if A[i]<=W:
        # セットに記録
        Weight.add(A[i])
 
# おもりを2個選ぶ場合
# i=0~(N^1)
for i in range(N):
    # j=(i+1)~(N-1)
    for j in range(i+1,N):
        # 重さの合計がW以下ならば
        if A[i]+A[j]<=W:
            # セットに記録
            Weight.add(A[i]+A[j])
 
# おもりを3個選ぶ場合
# i=0~(N^1)
for i in range(N):
    # j=(i+1)~(N-1)
    for j in range(i+1,N):
        # k=(j+1)~(N-1)
        for k in range(j+1,N):
            # 重さの合計がW以下ならば
            if A[i]+A[j]+A[k]<=W:
                # セットに記録
                Weight.add(A[i]+A[j]+A[k])
 
# 種類数=setの長さを出力
print(len(Weight))

ABC251 C

# 入力の受け取り
N=int(input())
 
# defaultdictをインポート
from collections import defaultdict
 
# 提出された文字列を記録する
# デフォルト値は0
Submitted=defaultdict(int)
 
# 答えの番号
AnsNo=0
# 最高得点
AnsPoint=0
 
# i=1~N
for i in range(1,N+1):
    # 入力の受け取り(文字列で受け取り)
    S,T=map(str,input().split())
 
    # Tを整数へ変換
    T=int(T)
 
    # オリジナルならば
    # ⇔0(デフォルト値)が記録されていたら
    if Submitted[S]==0:
        # 出てきた文字列として1を記録
        Submitted[S]=1
 
        # それまでの最高得点を上回っていたら
        if AnsPoint<T:
            # 答えの番号を更新
            AnsNo=i
            # 最高得点を更新
            AnsPoint=T
 
# 答えの出力
print(AnsNo)

# 入力の受け取り
N=int(input())
 
# 提出済みの文字列を記録するセット
Submitted=set()
 
# オリジナルの点数、文字列を記録するリスト
Original=[]
 
# i=1~N
for i in range(1,N+1):
    # 入力の受け取り(文字列で受け取り)
    S,T=map(str,input().split())
 
    # Tを整数へ変換
    T=int(T)
 
    # オリジナルならば
    # ⇔SがSubmittedに含まれていなければ
    if S not in Submitted:
        # Submittedに追加
        Submitted.add(S)
        # 点数、文字列を追加
        Original.append([T,-i])
 
# 点数(先頭の要素)の大きい順に並び替え
Original.sort(reverse=True)
 
# 答えの出力
print(-Original[0][1])

ABC252 A

# 入力の受け取り
N=int(input())
 
# 文字コード→文字へ変換して出力
print(chr(N))

# 入力の受け取り
N=int(input())
 
# Nが97ならば「a」を出力
if N==97:print("a")
elif N==98:print("b")
elif N==99:print("c")
elif N==100:print("d")
elif N==101:print("e")
elif N==102:print("f")
elif N==103:print("g")
elif N==104:print("h")
elif N==105:print("i")
elif N==106:print("j")
elif N==107:print("k")
elif N==108:print("l")
elif N==109:print("m")
elif N==110:print("n")
elif N==111:print("o")
elif N==112:print("p")
elif N==113:print("q")
elif N==114:print("r")
elif N==115:print("s")
elif N==116:print("t")
elif N==117:print("u")
elif N==118:print("v")
elif N==119:print("w")
elif N==120:print("x")
elif N==121:print("y")
elif N==122:print("z")

ABC252 B

# 入力の受け取り
N,K=map(int,input().split())
# 0番目を埋めるために適当な数(0)を埋める
A=[0]+list(map(int,input().split()))
B=list(map(int,input().split()))
 
# Aの最大値
Amax=max(A)
 
# 食べる可能性のある食品の番号リスト
Eat=[]
 
# i=1~N
for i in range(1,N+1):
    # A[i]=(Aの最大値)ならば
    if A[i]==Amax:
        # リストへ追加
        Eat.append(i)
 
# X：Eatの要素を順番に代入
for X in Eat:
    # xがBに含まれていれば
    if X in B:
        # 「Yes」を出力
        print("Yes")
        # 終了
        exit()
 
# 「No」を出力
print("No")

# 入力の受け取り
N,K=map(int,input().split())
A=[0]+list(map(int,input().split()))
B=list(map(int,input().split()))
 
# 答え：最初は「No」
ans="No"
 
# i：Bの要素を順に代入
for i in B:
    # A[i]=(Aの最大値)ならば
    if A[i]==max(A):ans="Yes"
 
# 「No」を出力
print(ans)

ABC252 C

# 入力の受け取り
N=int(input())
 
# 「0」~「9」の表示秒数記録リスト
# 0の表示秒数：[0,1,2,3]⇔Time[0]=[0,1,2,3]　というように記録する
Time=[[] for i in range(10)]
 
# 各数の出現回数を数えるリスト
# Count[1][2]=3なら「1」の表示秒数に2秒が3回表示された　という意味
Count=[[0]*10 for i in range(10)]
 
# N回
for i in range(N):
    # 入力の受け取り
    S=input()
   
    # x=0~9
    for x in range(10):
        # Sのx文字目を整数へ変換
        Sint=int(S[x])
 
        # x秒の出現回数をプラス1
        Count[Sint][x]+=1
        # 表示秒数を記録
        # (出現回数-1)*10をプラスする
        Time[Sint].append(x+(Count[Sint][x]-1)*10)
 
# 答え
# 初期値は大きめの数にしておく
ans=10**15
 
# i=0~9
for i in range(10):
    # 「i」を揃えるための秒数
    # ⇔Time[i]の最大
    # これまでの答えより小さければ更新
    ans=min(ans,max(Time[i]))
 
# 答えを出力
print(ans)

ABC252 D

# 入力の受け取り
N=int(input())
A=list(map(int,input().split()))
 
# 出現回数の確認リスト
Count=[0]*(10**6)
 
# X：Aの各要素を順に代入
for X in A:
    # 出現回数をカウント
    Count[X]+=1
 
# i=0~(10^6-2)
for i in range(10**6-1):
    # 一つ前の数を足していく
    Count[i+1]+=Count[i]
 
# 上記の処理でCount[x]=「Aにあるxより小さい要素の数」となる
 
# 答え
ans=0
 
# X：Aの各要素を順に代入
for X in A:
    # (「より小さい数」の数)*(「より大きい数」の数)
    ans+=Count[X-1]*(N-Count[X])
 
# 答えを出力
print(ans)

ABC253 A

# 入力の受け取り
a,b,c=map(int,input().split())
 
# a≤b≤c or c≤b≤aになっていれば
if a<=b<=c or c<=b<=a:
    # 「Yes」を出力
    print("Yes")
# そうでなければ
else:
    # 「No」を出力
    print("No")

# 入力の受け取り
X=list(map(int,input().split()))
 
# statisticsをインポート
import statistics
 
# X[1](=b)=(Xの中央値)ならば
if X[1]==statistics.median(X):
    # 「Yes」を出力
    print("Yes")
# そうでなければ
else:
    # 「No」を出力
    print("No")

ABC253 B

# 入力の受け取り
H,W=map(int,input().split())
 
# 駒の座標格納用リスト
p=[]
 
# 行：G=0~(H-1)
for G in range(H):
    # 入力の受け取り
    S=input()
 
    # 列：R=0~(W-1)
    for R in range(W):
        # SのR文字目が「o」ならば
            if S[R]=="o":
                # 座標を記録
                p.append([G,R])
 
# 行方向の移動量
Gmove=abs(p[0][0]-p[1][0])
# 列方向の移動量
Rmove=abs(p[0][1]-p[1][1])
 
# 答えの出力
print(Gmove+Rmove)

ABC253 C

# 入力の受け取り
Q=int(input())
 
# defaultdictのインポート
from collections import defaultdict
 
# それぞれの数がSにいくつ入っているか確認する連想配列
# 初期値は0
Count=defaultdict(int)
 
# heapqのインポート
import heapq
# 最大値を取り出す用
MaxQue=[]
# 最小値を取り出す用
MinQue=[]
 
# Q回
for i in range(Q):
    # 入力の受け取り
    # クエリの種類によって長さが違うからリストで受け取り
    query=list(map(int,input().split()))
 
    # クエリ1
    if query[0]==1:
        # xを確認
        x=query[1]
 
        # xがSに1個増えた
        Count[x]+=1
 
        # heap queueへ入れる
        heapq.heappush(MinQue,x)
        # heap queueは最小値しか取り出せないから最大値の方へは「-x」を入れる
        heapq.heappush(MaxQue,-x)
 
    # クエリ2
    elif query[0]==2:
        # x,cを確認
        x=query[1]
        c=query[2]
 
        # Sからmin(c,Sに入っている個数)個のxを削除
        Count[x]-=min(c,Count[x])
 
    # クエリ3
    else:
        # Sの最小値を取り出し
        SMin=heapq.heappop(MinQue)
 
        # SMinが0個である場合
        while Count[SMin]==0:
            # 次の最小値を取り出し
            SMin=heapq.heappop(MinQue)
 
        # Sの最大値を取り出し
        SMax=heapq.heappop(MaxQue)
        # マイナスを取る⇔(-1)を掛ける
        SMax*=-1
        # SMaxが0個である場合
        while Count[SMax]==0:
            # 次の最大値を取り出す
            SMax=heapq.heappop(MaxQue)
            # マイナスを取る⇔(-1)を掛ける
            SMax*=-1
 
        # (最大値-最小値)を出力
        print(SMax-SMin)
 
        # 最小値、最大値をheap queueへ戻す
        heapq.heappush(MinQue,SMin)
        heapq.heappush(MaxQue,-SMax)

ABC253 D

# 最小公倍数の計算を行う関数
import math
def lcm(x, y):
    return (x * y) // math.gcd(x, y)
 
# 入力の受け取り
N,A,B=map(int,input().split())
 
# 等差数列の和
# n：項数　a：初項　d：公差
def TousaSum(n,a,d):
    return n*(2*a+(n-1)*d)//2
 
# 答え
# 1~Nまでの和
ans=TousaSum(N,1,1)
 
# Aの倍数の和を引く
ans-=TousaSum(N//A,A,A)
# Bの倍数の和を引く
ans-=TousaSum(N//B,B,B)
# 最小公倍数
ABlcm=lcm(A,B)
# A,Bの最小公倍数の和を引く
ans+=TousaSum(N//ABlcm,ABlcm,ABlcm)
 
# 答えの出力
print(ans)

ABC253 E

# pypyで提出
 
# 入力の受け取り
N,M,K=map(int,input().split())
 
# 余りの定義
Mod=998244353
 
# (1)表を作る
dp=[[0]*(M+1) for i in range(N+1)]
 
# (2)すぐにわかるところを埋める
# ・(1≤x≤M)dp[1][x]=1
# i=1~M
for i in range(1,M+1):
    # 1を埋める
    dp[1][i]=1
 
# (3)表の小さい方から答えにたどり着くまで埋める
# i=2~N
for i in range(2,N+1):
 
    # (i-1)行目の累積和の計算
    CumSum=[0]*(M+1)
    # x=1~M
    for x in range(1,M+1):
        CumSum[x]=CumSum[x-1]+dp[i-1][x]
        CumSum[x]%=Mod
 
    # x=1~M
    for x in range(1,M+1):
       
        # K=0
        # ・(2≤i)dp[i][x]=CumSum[M]
        if K==0:
            dp[i][x]=CumSum[M]
 
        # 0<K
        else:
            # ・(2≤i,x-K<1)dp[i][x]=CumSum[M]-CumSum[x+K-1]
            # ・(2≤i,M<x+K)dp[i][x]=CumSum[x-K]
            # ・(2≤i,それ以外)dp[i][x]=(CumSum[M]-CumSum[x+K-1])+CumSum[x-K]
            # 条件を満たしている場合だけ足し算する
            if 1<=x-K:
                dp[i][x]+=CumSum[x-K]
            if x+K<=M:
                dp[i][x]+=CumSum[M]-CumSum[x+K-1]
 
        # 余りを取る
        dp[i][x]%=Mod
 
# (4)答えを出力する
# 答え
ans=0
 
# dp[N][1]~dp[N][M]の和
# x=1~M
for x in range(1,M+1):
    # N行目x列目を足す
    ans+=dp[N][x]
    # 余りを取る
    ans%=Mod
 
# 答えの出力
print(ans)

ABC254 A

# 入力の受け取り
N=input()
 
# 1文字目と2文字目を連結して出力
print(N[1]+N[2])

ABC254 B

# 入力の受け取り
N=int(input())
 
# 二次元配列を作る
a=[[0]*N for i in range(N)]
 
# i=0~(N-1)
for i in range(N):
    # j=0~i
    for j in range(i+1):
 
        # j=0 または j=iの場合
        if j==0 or j==i:
            a[i][j]=1
       
        # それ以外
        else:
            a[i][j]=a[i-1][j-1]+a[i-1][j]
 
# i=0~(N-1)
for i in range(N):
    # a[i]の0~i番目までを出力
    print(*a[i][:i+1])

ABC254 C

# 入力の受け取り
N,K=map(int,input().split())
a=list(map(int,input().split()))
 
# ソート後のA
aSorted=sorted(a)
 
# defaultdictをインポート
from collections import defaultdict
 
# a[i],a[i+K],a[i+2K],...に出てくる数字をカウントする連想配列
Count=defaultdict(int)
 
# i=0~(K-1)
for i in range(K):
 
    x=0
    # インデックスの範囲内である限り
    while i+K*x<N:
        # a[i+K*x]の個数をカウント
        Count[a[i+K*x]]+=1
        # 次のxへ
        x+=1
 
    x=0
    # インデックスの範囲内である限り
    while i+K*x<N:
        # ソート後のaについてaSorted[i+K*x]の個数をマイナス
        Count[aSorted[i+K*x]]-=1
        # もし個数がマイナスになったら
        if Count[aSorted[i+K*x]]<0:
            # ソート前とソート後で個数が違う
            # ⇔「No」を出力
            print("No")
            # 終了
            exit()
       
        # 次のxへ
        x+=1
 
# 「Yes」を出力
print("Yes")

ABC254 D

# pypyで提出
 
# 素因数分解
# 引数：x　→　返り値：xの素因数リスト
# x=1の場合は空のリストを返す
def PrimeFactorize(x):
    # もしx=1ならば
    if x==1:
        # 空のリストを返す
        return []
    # 素因数を格納するリスト
    PrimeList=[]
    # i=2,3,4,...で試し割り
    i=2
    # i≤√xすなわちi**2≤xの範囲で試し割り
    while i**2<=x:
        # もしiで割り切れたら
        if x%i==0:
            # iを素因数に追加
            PrimeList.append(i)
            # xをiで割る
            x//=i
        # iで割り切れなかったら
        else:
            # 次のiへ
            i+=1
    # 試し割りが終わった時xが1でなければ
    if x!=1:
        # 素因数にxを追加
        PrimeList.append(x)
    # 素因数のリストを返す
    return PrimeList
 
# 入力の受け取り
N=int(input())
 
# N=1の場合は例外ケースとして処理
if N==1:
    print(1)
    exit()
   
# 平方数のリスト
S=[]
 
# i=0~Nまで
for i in range(N+1):
    # 平方数を格納
    S.append(i**2)
 
# 二分探索
def Nibutan(j):
    # 左端
    l=0
    # 右端
    r=N
 
    # 1<(右端)-(左端)　の間
    while 1<r-l:
        # 中央
        c=(l+r)//2
 
        # S[中央]*jがN以下の場合
        if S[c]*j<=N:
            # 左端=中央と更新
            l=c
        # そうでない場合
        else:
            # 右端=中央と更新
            r=c
   
    # 左端を返す
    return l
 
# 答え
ans=0
 
# i=1~N
for i in range(1,N+1):
   
    # 初期値の割当
    j=1
 
    # iの素因数分解結果
    P=PrimeFactorize(i)
 
    # x：iの素因数それぞれについて
    for x in set(P):
        # xが素因数リストに奇数個含まれていれば
        if P.count(x)%2==1:
            # jに掛ける
            j*=x
       
    # j*(平方数)≤Nとなる最大の(平方数)が何番目かを確認し、答えにカウント
    ans+=Nibutan(j)
 
# 答えの出力
print(ans)

ABC255 A

# 入力の受け取り
R,C=map(int,input().split())
A11,A12=map(int,input().split())
A21,A22=map(int,input().split())
 
# (R,C)=(1,1)の場合
if R==1 and C==1:
    # 答えの出力
    print(A11)
# (R,C)=(1,2)の場合
elif R==1 and C==2:
    # 答えの出力
    print(A12)
# (R,C)=(2,1)の場合
elif R==2 and C==1:
    # 答えの出力
    print(A21)
# それ以外((R,C)=(2,2))
else:
    # 答えの出力
    print(A22)

ABC255 B

# 入力の受け取り
N,K=map(int,input().split())
A=list(map(int,input().split()))
 
# 座標の格納リスト
# 0番目を埋めるために[0,0]を入れておく
p=[[0,0]]
 
# N回
for i in range(N):
    # 入力の受け取り
    X,Y=map(int,input().split())
    # 座標の記録
    p.append([X,Y])
 
# 表を作る
dist=[[0]*(N+1) for i in range(K)]
 
# ルートの計算のためmathからsqrtをインポート
from math import sqrt
 
# 人aと人bの距離の計算関数
def CalcDist(a,b):
    return sqrt((p[a][0]-p[b][0])**2+(p[a][1]-p[b][1])**2)
 
# 行：G=0~(K-1)
for G in range(K):
    # 列：R=1~N
    for R in range(1,N+1):
        # 距離を計算して表を更新
        dist[G][R]=CalcDist(A[G],R)
 
# それぞれの列の最小値を確認するリスト
RMin=[0]*(N+1)
 
# 列：R=1~N
for R in range(1,N+1):
    # 距離
    d=10**10
    # 行：G=0~(K-1)
    for G in range(K):
        # d=ここまでのdと表の値の小さい方
        d=min(d,dist[G][R])
   
    # 最小値を記録
    RMin[R]=d
 
# (列ごとの最小値)の最大値
print(max(RMin))

ABC255 C

# 入力の受け取り
X,A,D,N=map(int,input().split())
 
# Sのi項目を計算する関数
def S(i):
    return A+(i-1)*D
 
# Dがプラスの場合の二分探索
def NibutanPlus(X):
    # (1)区間[左,右]を指定する
    l=1
    r=N
 
    # (4)1<(右-左)となっている間(2)~(4)を繰り返す
    while 1<r-l:
        # (2)中央=(左+右)//2が条件を満たすか確認
        # (3)(2)の結果より左または右を更新する
        c=(l+r)//2
 
        if S(c)<=X:
            # 左=中央と更新
            l=c
        else:
            # 右=中央と更新
            r=c
 
    # l,rを返す
    return l,r
 
# Dがマイナスの場合の二分探索
def NibutanMinus(X):
    l=1
    r=N
 
    while 1<r-l:
        c=(l+r)//2
 
        if S(c)<=X:
            r=c
        else:
            l=c
 
    return l,r
 
# Dが0の場合
if D==0:
    # |A-X|が答え
    print(abs(A-X))
 
# Dがプラスの場合
elif 0<D:
    # Xが初項より小さい場合
    if X<A:
        # (A-X)が答え
        print(A-X)
    # Xが末項より大きい場合
    elif S(N)<=X:
        # (X-末項)が答え
        print(X-S(N))
    # 上記以外
    else:
        # 二分探索でどの項の間にあるか確認
        l,r=NibutanPlus(X)
        # 差が小さいほうが答え
        print(min(X-S(l),S(r)-X))
 
# Dがマイナスの場合
else:
    # Xが初項より大きい場合
    if A<X:
        # (X-A)が答え
        print(X-A)
    # Xが末項より小さい場合
    elif X<=S(N):
        # (末項-X)が答え
        print(S(N)-X)
    # それ以外
    else:
        # 二分探索でどの項の間にあるか確認
        l,r=NibutanMinus(X)
        # 差が小さいほうが答え
        print(min(S(l)-X,X-S(r)))

ABC255 D

# 入力の受け取り
N,Q=map(int,input().split())
# A[0]を埋めておき、1インデックスにする
A=[0]+list(map(int,input().split()))
 
# Aをソート
A.sort()
 
# 二分探索
def Nibutan(X):
    # (1)区間[左,右]を指定する
    l=1
    r=N
 
    # (4)1<(右-左)となっている間(2)~(4)を繰り返す
    while 1<r-l:
        # (2)中央=(左+右)//2が条件を満たすか確認
        # (3)(2)の結果より左または右を更新する
        c=(l+r)//2
 
        if A[c]<=X:
            l=c
        else:
            r=c
 
    # 左端を返す
    return l
 
# 累積和の計算
ACum=[0]*(N+1)
for i in range(1,N+1):
    ACum[i]=ACum[i-1]+A[i]
 
# Q回
for i in range(Q):
    # 入力の受け取り
    X=int(input())
 
    # X<A1なら
    if X<A[1]:
        # (A1~ANの和)-X*N
        ans=ACum[N]-X*N
    # AN≤Xなら
    elif A[N]<=X:
        # X*N-(A1~ANの和)
        ans=X*N-ACum[N]
    # 上記以外
    else:
        # Xが何番目の要素の間にあるか確認
        l=Nibutan(X)
 
        # (X*l-(A1~Alの和))+(A(l+1)~ANの和)-X*(N-l)
        ans=X*l-ACum[l]+(ACum[N]-ACum[l])-X*(N-l)
 
    # 答えの出力
    print(ans)

ABC256 A

# 入力の受け取り
N=int(input())
 
# 2のN乗を出力
print(2**N)

ABC256 B

# 入力の受け取り
N=int(input())
A=list(map(int,input().split()))
 
# (1)マス目Sqを作る。最初はSq[0]=1,Sq[1]=0,Sq[2]=0,Sq[3]=0となるように。
Sq=[1,0,0,0]
# Pを作る
P=0
 
# i=0~(N-1)
for i in range(N):
    # (2)操作後の駒の場所を記録するNewSqを作る。
    NewSq=[1,0,0,0]
    # k=0~3
    for k in range(4):
        # (3)駒を移動させて、NewSqへ記録。
        # マスkが1ならば
        if Sq[k]==1:
            # k+A[i]が4未満ならば
            if k+A[i]<4:
                # 駒を移動
                NewSq[k+A[i]]=1
            # そうでなければ
            else:
                # Pにプラス1
                P+=1
   
    # (4)SqをNewSqで更新。
    Sq=NewSq
 
# Pを出力
print(P)

ABC256 C

# 入力の受け取り
h1,h2,h3,w1,w2,w3=map(int,input().split())
 
# 答えのカウント
ans=0
 
# M11=1~28
for M11 in range(1,29):
    # M12=1~28
    for M12 in range(1,29):
        # M21=1~28
        for M21 in range(1,29):
            # M22=1~28
            for M22 in range(1,29):
                # それぞれの値を計算
                M13=h1-(M11+M12)
                M23=h2-(M21+M22)
                M31=w1-(M11+M21)
                M32=w2-(M12+M22)
                M33=h3-(M31+M32)
               
                # ・全て正の整数(0より大きい)
                if 0<M13 and 0<M23 and 0<M31 and 0<M32 and 0<M33:              
                    # ・M13+M23+M33==w3も成り立つ
                    if M13+M23+M33==w3:
                        # 答えにカウント
                        ans+=1
 
# 答えの出力
print(ans)

ABC256 D

# 入力の受け取り
N=int(input())
 
# 区間の情報を格納するリスト
LR=[]
 
# N回
for i in range(N):
    # 入力の受け取り
    L,R=map(int,input().split())
    # 区間の情報を格納
    LR.append([L,R])
 
# 左側の小さい順にソート
LR.sort()
 
# 今の区間左側
NowL=LR[0][0]
# 今の区間右側
NowR=LR[0][1]
 
# i=1~(N-1)
for i in range(1,N):
    # 次の(i番目の)区間左側
    NextL=LR[i][0]
    # 次の(i番目の)区間右側
    NextR=LR[i][1]
 
    # ・一部カバーされる
    if NextL<=NowR and NowR<NextR:
        # それまでに作った区間の右端だけ延長する
        NowR=NextR
 
    # ・完全に分離している
    elif NowR<NextL:
        # 新しい区間を作る
        print(NowL,NowR)
        # 今の区間を更新
        NowL=NextL
        NowR=NextR
 
# 最後に区間を出力
print(NowL,NowR)

ABC257 A

# 入力の受け取り
N,X=map(int,input().split())
 
# 空の文字列を用意
S=""
 
# 「A」をN個くっつける
S+="A"*N
# 「B」をN個くっつける
S+="B"*N
S+="C"*N
S+="D"*N
S+="E"*N
S+="F"*N
S+="G"*N
S+="H"*N
S+="I"*N
S+="J"*N
S+="K"*N
S+="L"*N
S+="M"*N
S+="N"*N
S+="O"*N
S+="P"*N
S+="Q"*N
S+="R"*N
S+="S"*N
S+="T"*N
S+="U"*N
S+="V"*N
S+="W"*N
S+="X"*N
S+="Y"*N
S+="Z"*N
 
# 答えを出力
print(S[X-1])

# 入力の受け取り
N,X=map(int,input().split())
 
# 空の文字列を用意
S=""
 
# i=65~90
for i in range(65,91):
    # (文字コードi)の文字をN個くっつける
    S+=chr(i)*N
 
# 答えを出力
print(S[X-1])

ABC257 B

# 入力の受け取り
N,K,Q=map(int,input().split())
A=list(map(int,input().split()))
L=list(map(int,input().split()))
 
# Nマスのマス目を用意
# 0ならば駒がない
# 1ならば駒がある
S=[0]*(N+1)
 
# i=0~(K-1)
for i in range(K):
    # A[i]番目のマスに駒を置く
    S[A[i]]=1
 
# i=0~(Q-1)
for i in range(Q):
    # 何番目の駒か数える
    Count=0
   
    # Now=1~N
    # Now=今確認しているマス目
    for Now in range(1,N+1):
        # もしマス目Nowに駒が置いてあれば
        if S[Now]==1:
            # カウントする
            Count+=1
            # もしL[i]番目の駒ならば
            if Count==L[i]:
                # もしNow<N(一番右のマスでない)　かつ　1つ右のマスに駒がないならば
                if Now<N and S[Now+1]==0:
                    # 一つ右に駒を移動
                    S[Now+1]=1
                    # もとのマスに駒はなくなる
                    S[Now]=0
                    # 次のiへ
                    break
 
# 答え
ans=[]
 
# i=1~N
for i in range(1,N+1):
    # i番目のマスに駒があれば
    if S[i]==1:
        # 答えに追加
        ans.append(i)
 
# 答えの出力
# (「*」をつけると[]なしで出力できる)
print(*ans)

ABC257 C

# 入力の受け取り
N=int(input())
S=input()
W=list(map(int,input().split()))
 
# 子供リスト
Child=[]
# 大人リスト
Adult=[]
 
# i=0~(N-1)
for i in range(N):
    # 子供なら
    if S[i]=="0":
        # 子供リストへ追加
        Child.append(W[i])
    # 大人なら
    else:
        # 大人リストへ追加
        Adult.append(W[i])
 
# リストの長さを確認
CN=len(Child)
AN=len(Adult)
 
# 答え
Ans=0
 
# ソート
Child.sort()
Adult.sort()
 
# 正しい判定をされる子供の人数
k=0
# i=0~(Adultの長さ)
for i in range(AN):
    # X=大人の小さい方からi人目
    X=Adult[i]
    # 正しい判定をされる大人の人数
    Count=AN-i
 
    # k<(子供リストの長さ)　かつ　小さい方からk番目の子供<X　ならば
    while k<CN and Child[k]<X:
        # 正しい判定をされる子供の人数をカウント
        k+=1
   
    # 正しい判定をされる子供の人数をプラス
    Count+=k
 
    # これまでの答えより多ければ答えを更新
    Ans=max(Ans,Count)
 
# 大きい順にソートし直す
Adult.sort(reverse=True)
Child.sort(reverse=True)
 
# 正しい判定をされる大人の人数
k=0
# i=0~(Childの長さ)
for i in range(CN):
    # X=子供の大きい方からi人目+0.1
    X=Child[i]+0.1
    # 正しい判定をされる子供の人数
    Count=CN-i
 
    # k<(大人リストの長さ)　かつ　大きい方からk番目の大人≤X　ならば
    while k<AN and X<=Adult[k]:
        # 正しい判定をされる大人の人数をカウント
        k+=1
   
    # 正しい判定をされる大人の人数をプラス
    Count+=k
 
    # これまでの答えより多ければ答えを更新
    Ans=max(Ans,Count)
 
# 答えの出力
print(Ans)

ABC258 A

# 入力の受け取り
K=int(input())
 
# Kが60未満なら
if K<60:
    # K=0~9なら(一桁なら)
    if 0<=K<=9:
        # 「21：」+「0」+(Kを文字に変換)　を出力
        print("21:"+"0"+str(K))
    # それ以外なら(11~59分なら)
    else:
        # 「21：」+(Kを文字に変換)　を出力
        print("21:"+str(K))
# それ以外なら(Kが60以上)
else:
    # 60マイナスする
    K-=60
 
    # K=0~9なら(一桁なら)
    if 0<=K<=9:
        # 「22：」+「0」+(Kを文字に変換)　を出力
        print("22:"+"0"+str(K))
    # それ以外なら(11~59分なら)
    else:
        # 「22：」+(Kを文字に変換)　を出力
        print("22:"+str(K))

ABC258 B

# 入力の受け取り
N=int(input())
 
# マス目
Grid=[]
 
# N回
for i in range(N):
    # 入力の受け取り
    A=input()
    # 一文字ずつのリストへ展開
    A=list(A)
    # Gridへ記録
    Grid.append(A)
 
# 引数：(スタート行,スタート列,行方向,列方向)　→　マス目の数字を確認して値を返す
def Calc(G,R,GD,RD):
    # 結果
    result=""
    # i=0~(N-1)
    for i in range(N):
        # ((G+GD*i)%N,(R+RD*i)%N)マスの数字を記録
        result+=Grid[(G+GD*i)%N][(R+RD*i)%N]
    # 整数へ変換
    result=int(result)
    # 返す
    return result
 
# 答え
ans=0
 
# 行：G=0~(N-1)
for G in range(N):
    # 列：R=0~(N-1)
    for R in range(N):
        # (G,R)がスタートマス
        # 計算結果が今までの答えより大きければ更新
        # 上方向(-1,0)
        ans=max(ans,Calc(G,R,-1,0))
        # 右上方向(-1,1)
        ans=max(ans,Calc(G,R,-1,1))
        # 右方向(0,1)
        ans=max(ans,Calc(G,R,0,1))
        # 右下方向(1,1)
        ans=max(ans,Calc(G,R,1,1))
        # 下方向(1,0)
        ans=max(ans,Calc(G,R,1,0))
        # 左下方向(1,-1)
        ans=max(ans,Calc(G,R,1,-1))
        # 左方向(0,-1)
        ans=max(ans,Calc(G,R,0,-1))
        # 左上方向(-1,-1)
        ans=max(ans,Calc(G,R,-1,-1))
 
# 答えの出力
print(ans)

ABC258 C

# 入力の受け取り
N,Q=map(int,input().split())
S=input()
 
# スタート位置
Start=0
 
# Q回
for i in range(Q):
    # 入力の受け取り
    t,x=map(int,input().split())
 
    # クエリ1
    if t==1:
        # 「新しいスタート位置」=(「今のスタート位置」-x)%N
        Start=(Start-x)%N
    # クエリ2
    else:
        # ((「スタート位置」+(x-1))%N)番目の文字を出力する
        print(S[(Start+(x-1))%N])

ABC258 D

# 入力の受け取り
N,X=map(int,input().split())
 
# 答え　初期値は大きめにする
Ans=10**20
 
# ステージiまでをクリアするのにかかる時間
time=0
 
# i=1~(X,Nのうち小さい方)
for i in range(1,min(X,N)+1):
    # 入力の受け取り
    A,B=map(int,input().split())
 
    # 「ステージiまでクリアし、ステージiをクリアし続ける」のにかかる時間
    tmpAns=0
 
    # ステージiまでをクリアするのにかかる時間
    # (i-1)番目までをクリアするのにかかる時間+ステージiをクリアするのにかかる時間
    time+=A+B
 
    # (ステージiまでをクリアするのにかかる時間)を足す
    tmpAns+=time
 
    # ステージiまではクリアしている
    # ⇔i回はクリアしているので残り(X-i)回ステージiをクリアする
    tmpAns+=(X-i)*B
 
    # 答えが小さければ更新
    Ans=min(Ans,tmpAns)
 
# 答えの出力
print(Ans)

ABC259 A

# 入力の受け取り
N,M,X,T,D=map(int,input().split())
 
# X≤Mならば
if X<=M:
    # Tcm
    print(T)
# そうでなければ(M<X)
else:
    # (T-(X-M)D)cm
    print(T-(X-M)*D)

ABC259 B

# 入力の受け取り
a,b,d=map(int,input().split())
 
# mathライブラリのインポート
import math
 
# 度数法→弧度法へ変換
d=math.radians(d)
 
# 回転後の座標を計算
x=a*math.cos(d)-b*math.sin(d)
y=a*math.sin(d)+b*math.cos(d)
 
# 答えの出力
print(x,y)

ABC259 C

# 入力の受け取り
S=input()
T=input()
 
# 何文字連続しているか記録するリスト
Slist=[]
# 今連続している文字
Now=S[0]
# 連続している文字数
Count=1
 
# i=1~(N-1)
for i in range(1,len(S)):
    # Sのi文字目＝Nowなら
    if S[i]==Now:
        # カウントを増やす
        Count+=1
    # そうでなければ
    else:
        # リストへ記録
        Slist.append([Now,Count])
        # 次の文字へ
        Now=S[i]
        Count=1
# 最後のカウントを追加
Slist.append([Now,Count])
 
# Tも同じことをする
Tlist=[]
Now=T[0]
Count=1
 
for i in range(1,len(T)):
    if T[i]==Now:
        Count+=1
    else:
        Tlist.append([Now,Count])
        Now=T[i]
        Count=1
Tlist.append([Now,Count])
 
# ・文字の種類数が違う
if len(Slist)!=len(Tlist):
    # 「No」を出力
    print("No")
    # 終了
    exit()
 
# i=0~(Slistの長さ-1)
for i in range(len(Slist)):
    # S側の文字
    SMozi=Slist[i][0]
    # T側の文字
    TMozi=Tlist[i][0]
 
    # S側の文字数
    SCount=Slist[i][1]
    # T側の文字数
    TCount=Tlist[i][1]
 
    # ・文字の種類が違う
    if SMozi!=TMozi:
        print("No")
        exit()
 
    # ・S側よりT側の文字が多く、かつSが1文字
    elif SCount<TCount and SCount==1:
        print("No")
        exit()
   
    # ・T側よりS側の文字が多い
    elif TCount<SCount:
        print("No")
        exit()
   
# 「Yes」を出力
print("Yes")

ABC259 D

# pypyで提出
 
# UnionFind
class UnionFind:
    def __init__(self,n):
        self.n=n
        self.parent_size=[-1]*n
    def leader(self,a):
        if self.parent_size[a]<0: return a
        self.parent_size[a]=self.leader(self.parent_size[a])
        return self.parent_size[a]
    def merge(self,a,b):
        x,y=self.leader(a),self.leader(b)
        if x == y: return
        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
    def same(self,a,b):
        return self.leader(a) == self.leader(b)
 
# 入力の受け取り
N=int(input())
sx,sy,tx,ty=map(int,input().split())
 
# 円の情報
p=[]
 
# N回
for i in range(N):
    # 入力の受け取り
    x,y,r=map(int,input().split())
    # 記録
    p.append([x,y,r])
 
# UnionFindを用意
UF=UnionFind(N)
 
# A=0~(N-1)
for A in range(N):
    # B=(A+1)~(N-1)
    for B in range(A+1,N):
        # 円A,Bの座標と半径を取り出し
        xA,yA,rA=p[A]
        xB,YB,rB=p[B]
 
        # 中心間距離の二乗
        d=(xA-xB)**2+(yA-YB)**2
 
        # 乗り換え可能なら
        if (rB-rA)**2<=d<=(rB+rA)**2:
            # 連結
            UF.merge(A, B)
 
# スタートの点が載っている円
Start=[]
# ゴールの点が載っている円
Goal=[]
 
# i=0~(N-1)
for i in range(N):
    # i番目の円の中心、半径の取り出し
    xi,yi,ri=p[i]
 
    # スタートの点が円周上にあれば
    if (sx-xi)**2+(sy-yi)**2==ri**2:
        # 記録
        Start.append(i)
 
    # ゴールの点が円周上にあれば
    if (tx-xi)**2+(ty-yi)**2==ri**2:
        # 記録
        Goal.append(i)
 
# x：スタートの点が載っている円
for x in Start:
    # y：ゴールの点が載っている円
    for y in Goal:
        # 連結なら
        if UF.same(x,y)==True:
            # 「Yes」を出力
            print("Yes")
            # 終了
            exit()
 
# 「No」を出力
print("No")

ABC260 A

# 入力の受け取り
S=input()
 
# 「a」の個数が1個ならば
if S.count("a")==1:
    # 「a」を出力
    print("a")
elif S.count("b")==1:
    print("b")
elif S.count("c")==1:
    print("c")
elif S.count("d")==1:
    print("d")
elif S.count("e")==1:
    print("e")
elif S.count("f")==1:
    print("f")
elif S.count("g")==1:
    print("g")
elif S.count("h")==1:
    print("h")
elif S.count("i")==1:
    print("i")
elif S.count("j")==1:
    print("j")
elif S.count("k")==1:
    print("k")
elif S.count("l")==1:
    print("l")
elif S.count("m")==1:
    print("m")
elif S.count("n")==1:
    print("n")
elif S.count("o")==1:
    print("o")
elif S.count("p")==1:
    print("p")
elif S.count("q")==1:
    print("q")
elif S.count("r")==1:
    print("r")
elif S.count("s")==1:
    print("s")
elif S.count("t")==1:
    print("t")
elif S.count("u")==1:
    print("u")
elif S.count("v")==1:
    print("v")
elif S.count("w")==1:
    print("w")
elif S.count("x")==1:
    print("x")
elif S.count("y")==1:
    print("y")
elif S.count("z")==1:
    print("z")
# それ以外なら
else:
    # 「-1」を出力
    print(-1)

# 入力の受け取り
S=input()
 
# ・Sの0文字目≠Sの1文字目　かつ　Sの0文字目≠Sの2文字目 → 答え：Sの0文字目
if S[0]!=S[1] and S[0]!=S[2]:print(S[0])
# ・上記でなく　Sの0文字目≠Sの1文字目　かつ　Sの1文字目≠Sの2文字目 → 答え：Sの1文字目
elif S[0]!=S[1] and S[1]!=S[2]:print(S[1])
# ・上記でなく　Sの0文字目≠Sの2文字目　かつ　Sの1文字目≠Sの2文字目 → 答え：Sの2文字目
elif S[0]!=S[2] and S[1]!=S[2]:print(S[2])
# ・上記全て成り立たない → 答え：-1
else:print(-1)

ABC260 B

# 入力の受け取り
N,X,Y,Z=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
 
# 合格者のリスト
ans=[]
 
# 数学の点数と受験番号リスト
MathP=[]
 
# i=0~(N-1)
for i in range(N):
    # 「数学の点数」,「受験番号のマイナス」を記録
    MathP.append([A[i],-(i+1)])
# 大きい順にソート
MathP.sort(reverse=True)
 
# リストの前からX人合格
# i=0~(X-1)
for i in range(X):
    # 答えに合格者の番号を格納
    ans.append(-MathP[i][1])
 
# 英語の点数と受験番号リスト
EngP=[]
 
# i=0~(N-1)
for i in range(N):
    # 合格者のリストに番号がなければ
    if (i+1) not in ans:
        # 「英語の点数」,「受験番号のマイナス」を記録
        EngP.append([B[i],-(i+1)])
# 大きい順にソート
EngP.sort(reverse=True)
 
# リストの前からY人合格
# i=0~(Y-1)
for i in range(Y):
    # 答えに合格者の番号を格納
    ans.append(-EngP[i][1])
 
# 数学と英語の合計点数と受験番号リスト
MEP=[]
 
# i=0~(N-1)
for i in range(N):
    # 合格者のリストに番号がなければ
    if (i+1) not in ans:
        # 「数学と英語の合計点数」,「受験番号のマイナス」を記録
        MEP.append([A[i]+B[i],-(i+1)])
# 大きい順にソート
MEP.sort(reverse=True)
 
# リストの前からZ人合格
# i=0~(Z-1)
for i in range(Z):
    # 答えに合格者の番号を格納
    ans.append(-MEP[i][1])
 
# 答えのリストをソート
ans.sort()
 
# x：ansの各要素
for x in ans:
    # xを出力
    print(x)

ABC260 C

# 入力の受け取り
N,X,Y=map(int,input().split())
 
# 赤い宝石の個数
Red=[0]*(N+1)
# 青い宝石の個数
Blue=[0]*(N+1)
 
# レベルNの赤い宝石が1個ある
Red[N]=1
 
# i=N~2　-1ずつ
for i in range(N,1,-1):
 
    # 赤い宝石を変換
    # 1個につきレベル(n-1)の赤い宝石1個に変換
    Red[i-1]+=Red[i]
    # 1個につきレベルnの青い宝石X個に変換
    Blue[i]+=Red[i]*X
    # レベルiの赤い宝石はなくなる
    Red[i]=0
 
    # 青い宝石を交換
    # 1個につきレベル(n-1)の赤い宝石1個に変換
    Red[i-1]+=Blue[i]
    # 1個につきレベル(n-1)の青い宝石Y個に変換
    Blue[i-1]+=Blue[i]*Y
    # レベルiの青い宝石はなくなる
    Blue[i]=0
 
# レベル1の青い宝石の個数を出力
print(Blue[1])

ABC260 D

# pypyで提出
 
class FenwickTree:
    def __init__(self,n):
        self._n=n
        self.data=[0]*n
    def add(self,p,x):
        p+=1
        while p<=self._n:
            self.data[p-1] +=x
            p+=p&-p
    def _sum(self,r):
        s=0
        while 0<r:
            s+=self.data[r-1]
            r-=r&-r
        return s
    def sum(self,l,r):
        r+=1
        return self._sum(r)-self._sum(l)
    def select(self,p):
        return self.sum(p,p)
 
# 入力の受け取り
N,K=map(int,input().split())
P=list(map(int,input().split()))
 
# FenwickTreeを用意
FT=FenwickTree(N+1)
 
# defaultdictのインポート
from collections import defaultdict
# 山の情報を管理
# (例)山2にカード2,3,8が入っているならDeck[2]=[2,3,8]
# 初期値は空のリスト
Deck=defaultdict(list)
 
# 山の番号管理
DeckNum=0
 
# カードが何番の山にあるか
# CardInDeck[1]=2　ならばカード「1」が2番の山にある
CardInDeck=[0]*(N+1)
 
# 答え
ans=[-1]*(N+1)
 
# 二分探索
# 場に見えているカードのうち、x以上で最小のものを探す
def Nibutan(x):
    # (1)左=区間の最小、右=区間の最大　とする
    l=x
    r=N
 
    # (4)1<(右-左)となっている間(2)~(4)を繰り返す
    while 1<r-l:
        # (2)中央=(左+右)//2が条件を満たすか確認
        c=(l+r)//2
 
        # FT[x]~FT[c]の区間和が1以上なら
        # (3)(2)の結果より左または右を更新する
        if 1<=FT.sum(x,c):
            # 右=中央と更新
            r=c
        # そうでなければ(FT[x]~FT[c]の区間和が0なら)
        else:
            # 左=中央と更新
            l=c
 
    # 右を返す
    return r
 
# i=0~(N-1)
for i in range(N):
 
    # K=1ならば
    if K==1:
        # カードP[i]を(i+1)ターン目に食べることを記録
        ans[P[i]]=i+1
 
    # FT[P[i]]~FT[N]の区間和が0ならば
    # ⇔表に見えている中にP[i]より大きい数字のカードはない
    elif FT.sum(P[i], N)==0:
        # 新しい山を作る
        # 山の番号をプラス1
        DeckNum+=1
        # DeckNum番目の山にP[i]を追加
        Deck[DeckNum].append(P[i])
        # P[i]が場に見えている表向きのカードになる
        FT.add(P[i],1)
        # P[i]はDeckNum番目の山にあるカードであることを記録する
        CardInDeck[P[i]]=DeckNum
 
    # そうでなければ(FT[P[i]]~FT[N]の区間和が1以上ならば)
    else:
        # a：場に見えている表向きのカードのうち、P[i]以上で最小のもの
        a=Nibutan(P[i])
        # カードaが置かれている山の番号
        aDeckNum=CardInDeck[a]
        # カードP[i]を山aDeckNumに置く
        Deck[aDeckNum].append(P[i])
 
        # カードaは場に見えている表向きのカードでなくなる
        FT.add(a,-1)
        # カードP[i]が場に見えている表向きのカードになる
        FT.add(P[i],1)
        # P[i]はaDeckNum番目の山にあるカードであることを記録する
        CardInDeck[P[i]]=aDeckNum
   
        # aDeckNum番目の山のカード枚数がK枚になったら
        # ⇔カードを食べる
        if len(Deck[aDeckNum])==K:
            # q：aDeckNum番目の山のカードそれぞれについて
            for q in Deck[aDeckNum]:
                # (i+1)ターン目に食べたことを記録
                ans[q]=i+1
               
            # P[i]が表向きで場にあるカードでなくなる
            # ⇔マイナス1して0にする
            FT.add(P[i], -1)
 
# i=1~N
for i in range(1,N+1):
    # 答えの出力
    print(ans[i])