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

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

ABC261 A

# 入力の受け取り
L1,R1,L2,R2=map(int,input().split())
 
# L1,L2のうち大きい方
Lmax=max(L1, L2)
# R1,R2のうち小さい方
Rmin=min(R1, R2)
 
# (Rmin-Lmax)がマイナスなら
if Rmin-Lmax<0:
    # 0を出力
    print(0)
# そうでなければ
else:
    # (Rmin-Lmax)を出力
    print(Rmin-Lmax)

# 入力の受け取り
L1,R1,L2,R2=map(int,input().split())
 
# 0か(R1,R2のうち小さい方)-(L1,L2のうち大きい方) の大きい方
print(max(0,min(R1,R2)-max(L1,L2)))

ABC261 B

# 入力の受け取り
N=int(input())
 
# 表
A=[]
 
# N回
for i in range(N):
    # 入力の受け取り
    S=input()
    # 一文字ずつリストへ展開
    Slist=list(S)
    # Tableへ追加
    A.append(Slist)
 
# i=0~(N-1)
for i in range(N):
    # j=0~(N-1)
    for j in range(N):
 
        # i=jの場合
        if i==j:
            # 次のjへ
            continue
 
        # A[i][j]="W"　かつ　A[j][i]≠"L"　の場合
        if A[i][j]=="W" and A[j][i]!="L":
            # 「incorret」を出力
            print("incorrect")
            # 終了
            exit()
        # A[i][j]="L"　かつ　A[j][i]≠"W"　の場合
        if A[i][j]=="L" and A[j][i]!="W":
            # 「incorret」を出力
            print("incorrect")
            # 終了
            exit()
        # A[i][j]="D"　かつ　A[j][i]≠"D"　の場合
        if A[i][j]=="D" and A[j][i]!="D":
            # 「incorret」を出力
            print("incorrect")
            # 終了
            exit()
 
# 「correct」を出力
print("correct")

ABC261 C

# 入力の受け取り
N=int(input())
 
# defaultdictをインポート
from collections import defaultdict
 
# Sの出現回数を記録する連想配列
SCount=defaultdict(int)
 
# N回
for i in range(N):
    # 入力の受け取り
    S=input()
 
    # Sの出現回数が0回ならば
    if SCount[S]==0:
        # 何もつけずに出力
        print(S)
    # Sの出現回数が1回以上ならば
    else:
        # 出現回数とかっこをつけて出力
        print(S+"("+str(SCount[S])+")")
    # 出現回数をプラス1
    SCount[S]+=1

ABC261 D

# pypyで提出
 
# 入力の受け取り
N,M=map(int,input().split())
# X[0]はてきとうな値で埋めておく
X=[0]+list(map(int,input().split()))
# ボーナスの値(ボーナスない箇所は0)
B=[0]*(N+1)
 
# M回
for i in range(M):
    # 入力の受け取り
    C,Y=map(int,input().split())
    # カウンタCでY円ボーナス
    B[C]=Y
 
# (1)表を作る
# 「i回目までのコイントスを行い、カウンタの値がkである場合の(i回目までの)最大金額」
dp=[[0]*(N+1) for i in range(N+1)]
 
# i=1~N
for i in range(1,N+1):
    # k=0~i
    for k in range(i+1):
        # k=0の場合
        if k==0:
            dp[i][k]=max(dp[i-1])
        # 1≤kの場合
        else:
            dp[i][k]=dp[i-1][k-1]+X[i]+B[k]
 
# 答え：N行目の最大値
print(max(dp[N]))

ABC262 A

# 入力の受け取り
Y=int(input())
 
# Yを4で割った余りが2なら
if Y%4==2:
    # Yを出力
    print(Y)
# (Y+1)を4で割った余りが2なら
elif (Y+1)%4==2:
    # (Y+1)を出力
    print(Y+1)
# (Y+2)を4で割った余りが2なら
elif (Y+2)%4==2:
    # (Y+2)を出力
    print(Y+2)
# (Y+3)を4で割った余りが2なら
elif (Y+3)%4==2:
    # (Y+3)を出力
    print(Y+3)

# 入力の受け取り
Y=int(input())
 
# 答えの出力
print(Y+(2-Y%4)%4)

ABC262 B

# 入力の受け取り
N,M=map(int,input().split())
 
# つながっている頂点を記録する二次元配列
# 最初は全ての初期値をFalseにする
connect=[[False]*(N+1) for i in range(N+1)]
 
# M回
for i in range(M):
    # 入力の受け取り
    U,V=map(int,input().split())
    # 頂点Uと頂点Vがつながっている⇔Trueと記録
    connect[U][V]=True
    connect[V][U]=True
 
# 答え
ans=0
 
# a=1~N
for a in range(1,N+1):
    # b=(a+1)~N
    for b in range(a+1,N+1):
        # c=(b+1)~N
        for c in range(b+1,N+1):
            # a,b,cが全てつながっていれば
            if connect[a][b]==True and connect[b][c]==True and connect[c][a]==True:
                # 答えにプラス1
                ans+=1
 
# 答えの出力
print(ans)

ABC262 C

# 入力の受け取り
N=int(input())
# a[0]を適当な数(=0)で埋めておく
a=[0]+list(map(int,input().split()))
 
# 答え
ans=0
 
# ・ai=i,aj=j
# ax=xとなっているものの個数
k=0
 
# i=1~N
for i in range(1,N+1):
    # a[i]=iならば
    if a[i]==i:
        # kにカウント
        k+=1
 
# kC2=(k*(k-1)//2)個
ans+=k*(k-1)//2
 
# ・ai=j,aj=i
# i=1~N
for i in range(1,N+1):
    # a[i]=j
    j=a[i]
    # i<j　かつ　a[j]=iならば
    if i<j and  a[j]==i:
        # 答えにカウント
        ans+=1
 
# 答えの出力
print(ans)

ABC263 A

# 入力の受け取り
Card=list(map(int,input().split()))
 
# 小さい順に並び替え
Card.sort()
 
# 0枚目と1枚目が同じ かつ 2枚目と3枚目と4枚目が同じ
if Card[0]==Card[1] and Card[2]==Card[3]==Card[4]:
    # 「Yes」を出力
    print("Yes")
# 0枚目と1枚目と2枚目が同じ かつ 3枚目と4枚目が同じ
elif Card[0]==Card[1]==Card[2] and Card[3]==Card[4]:
    # 「Yes」を出力
    print("Yes")
# どちらでもない
else:
    # 「No」を出力
    print("No")

ABC263 B

# 入力の受け取り
N=int(input())
# P[0]とP[1]をてきとうな値で埋める
P=[0]+[0]+list(map(int,input().split()))
 
# 世代を遡った回数
Count=1
 
# 人Nから辿っていく
i=N
# 人1にたどり着くまで
while P[i]!=1:
    # 回数のカウント
    Count+=1
    # P[i]の親へ
    i=P[i]
 
# 遡った回数を出力
print(Count)

ABC263 C

# 入力の受け取り
N,M=map(int,input().split())
 
# itertoolsのインポート
import itertools
# 重複なしの組み合わせ
# (1,2,3),(1,2,4),---,(7,8,9)
for p in itertools.combinations(range(1,M+1),N):
    # 答えの出力(*をつけると[]なしで出力できる)
    print(*p)

ABC263 D

# 入力の受け取り
N,L,R=map(int,input().split())
A=list(map(int,input().split()))
 
# fの計算
# A[0]を埋める
A=[0]+A
# fを作る(f(0)=0)
f=[0]*(N+1)
 
# i=1~N
for i in range(1,N+1):
    # fの計算
    f[i]=min(f[i-1]+A[i],L*i)
 
# Aをひっくり返す
A=A[::-1]
# A[0]を埋める
A=[0]+A
 
# gを作る(g(0)=0)
g=[0]*(N+1)
 
# i=1~N
for i in range(1,N+1):
    # fの計算
    g[i]=min(g[i-1]+A[i],R*i)
 
# 答え
ans=10**15
# i=1~N
for i in range(N+1):
    # これまでの答えとf[i]+g[N-i]の小さい方で更新
    ans=min(ans,f[i]+g[N-i])
 
# 答えの出力
print(ans)

ABC264 A

# 入力の受け取り
L,R=map(int,input().split())
 
# 「atcoder」をSへ格納
S="atcoder"
 
# (L-1)~(R-1)番目を出力
print(S[L-1:R])

ABC264 B

# 入力の受け取り
R,C=map(int,input().split())
# マス目を作る
# 最初は全てのマスが0
Grid=[[0]*16 for i in range(16)]
 
# i=1~15
for i in range(1,16):
    # 1行i列=1
    Grid[1][i]=1
    # 15行i列=1
    Grid[15][i]=1
    # i行1列=1
    Grid[i][1]=1
    # i行15列=1
    Grid[i][15]=1
 
# i=3~13
for i in range(3,14):
    Grid[3][i]=1
    Grid[13][i]=1
    Grid[i][3]=1
    Grid[i][13]=1
 
# i=5~11
for i in range(5,12):
    Grid[5][i]=1
    Grid[11][i]=1
    Grid[i][5]=1
    Grid[i][11]=1
 
# i=7~9
for i in range(7,10):
    Grid[7][i]=1
    Grid[9][i]=1
    Grid[i][7]=1
    Grid[i][9]=1
 
# R行C列が1ならば
if Grid[R][C]==1:
    # 「black」を出力
    print("black")
# R行C列が0ならば
else:
    # 「white」を出力
    print("white")

ABC264 C

# pypyで提出
 
# 入力の受け取り
H1,W1=map(int,input().split())
A=[]
 
# i=0~(H1-1)
for i in range(H1):
    # リストとして受け取り
    tmp=list(map(int,input().split()))
    # Aに追加
    A.append(tmp)
 
# 入力の受け取り
H2,W2=map(int,input().split())
B=[]
 
# i=0~(H2-1)
for i in range(H2):
    # リストとして受け取り
    tmp=list(map(int,input().split()))
    # Bに追加
    B.append(tmp)
 
# 行の2進数を作る(GyouBit=Gb)
for Gb in range(1<<H1):
    # 列の2進数を作る(RetuBit=Rb)
    for Rb in range(1<<W1):
        # 空の配列(Aremove)を作る
        Aremove=[]
 
        # i=0~(H1-1)
        for i in range(H1):
            # 0行目、1行目、...について、Gbの0桁目、1桁目を見て残す行か確認
            # ⇔Gbの右からi桁目と1をアンド演算して1なら残す
            if Gb>>i & 1 ==1:
 
                # (残す行なら)空の配列(Retu)を作る
                Retu=[]
 
                # k=0~(W1-1)
                for k in range(W1):
                    # 0列目、1列目、...について、Rbの0桁目、1桁目を見て残す行か確認
                    # ⇔Rbの右からi桁目と1をアンド演算して1なら残す
                    if Rb>>k & 1 ==1:
                        # 残す列なら要素をRetuへ追加
                        Retu.append(A[i][k])
 
                # RetuをAremoveへ追加
                Aremove.append(Retu)
                       
        # 操作後のAとBが一致したら
        if Aremove==B:
            # 「Yes」を出力
            print("Yes")
            # 途中終了
            exit()
 
# 「No」を出力
print("No")

ABC264 D

# 入力の受け取り
S=input()
# 「atcoder」をTに格納
T="atcoder"
 
# 1文字ずつリストへ展開
Slist=list(S)
 
# 答え
ans=0
 
# i=0~6
for i in range(7):
    # Tのi文字目がSlistの何番目か確認
    indx=Slist.index(T[i])
 
    # indxがiでない(正しい位置に来ていない)間
    while indx!=i:
        # indx番目と(indx-1)番目を入れ替え
        Slist[indx],Slist[indx-1]=Slist[indx-1],Slist[indx]
        # 次の文字へ
        indx-=1
        # 操作回数をカウント
        ans+=1
 
# 答えの出力
print(ans)

ABC265 A

# 入力の受け取り
X,Y,N=map(int,input().split())
 
# 1個ずつ買う場合
A=X*N
# 3個セットで買う場合
B=(N//3)*Y+(N%3)*X
 
# A,Bの小さい方が答え
print(min(A,B))

ABC265 B

# 入力の受け取り
N,M,T=map(int,input().split())
# A[0]を埋めるために適当な数字(0)を入れておく
A=[0]+list(map(int,input().split()))
 
# ボーナス部屋で増加する時間の記録リスト
Bonus=[0]*(N+1)
# M回
for i in range(M):
    # 入力の受け取り
    X,Y=map(int,input().split())
    # 部屋XでY増える
    Bonus[X]=Y
 
# i=1~(N-1)
for i in range(1,N):
    # 部屋(i+1)へ移動するためにA[i]時間消費する
    T-=A[i]
 
    # Tが0以下になったら
    if T<=0:
        # 「No」を出力
        print("No")
        # 終了
        exit()
       
    # (i+1)番目の部屋で増加する時間
    T+=Bonus[i+1]
 
# 「Yes」を出力
print("Yes")

ABC265 C

# 入力の受け取り
H,W=map(int,input().split())
 
# グリッド
G=[]
# H回
for i in range(H):
    # 入力の受け取り
    S=input()
    # 1文字ずつリストへ展開
    S=list(S)
    # グリッドに追加
    G.append(S)
 
# 通ったマスを記録する二次元配列
# 初期値は0
# 通ったマスは1にしていく
visited=[[0]*W for i in range(H)]
 
# 今の行(G)、列(R)
NowG,NowR=0,0
 
# 10^10回(大きな数なら何でもOK)
for i in range(10**10):
 
    # 今いるマスが訪問済みならば
    if visited[NowG][NowR]==1:
        # 「-1」を出力
        print(-1)
        # 終了
        exit()
 
    # 今いるマスを訪問済みにする
    visited[NowG][NowR]=1
 
    # 今いるマスが「U」ならば
    if G[NowG][NowR]=="U":
        # 今いるマスの行番号が1以上ならば(上に進んでも壁でないなら)
        if 1<=NowG:
            # 上に進む⇔行をマイナス1
            NowG-=1
        # そうでなければ(上マスが壁)
        else:
            # 今いるマスの座標を出力(1個ずれるので+1することに注意)
            print(NowG+1,NowR+1)
            # 終了
            exit()
   
    # 今いるマスが「R」ならば
    elif G[NowG][NowR]=="R":
        # 今いるマスの列番号が(W-2)以下ならば(右に進んでも壁でないなら)
        if NowR<=W-2:
            # 右に進む⇔列をプラス1
            NowR+=1
        else:
            # 今いるマスの座標を出力(1個ずれるので+1することに注意)
            print(NowG+1,NowR+1)
            # 終了
            exit()
 
    # 今いるマスが「D」ならば
    elif G[NowG][NowR]=="D":
        # 今いるマスの行番号が(H-2)以下ならば(下に進んでも壁でないなら)
        if NowG<=H-2:
            # 下に進む⇔行をプラス1
            NowG+=1
        else:
            # 今いるマスの座標を出力(1個ずれるので+1することに注意)
            print(NowG+1,NowR+1)
            # 終了
            exit()
 
    # 今いるマスが「L」ならば
    elif G[NowG][NowR]=="L":
        # 今いるマスの列番号が1以上ならば(左に進んでも壁でないなら)
        if 1<=NowR:
            # 左に進む⇔列をマイナス1
            NowR-=1
        else:
            # 今いるマスの座標を出力(1個ずれるので+1することに注意)
            print(NowG+1,NowR+1)
            # 終了
            exit()

ABC265 D

# 入力の受け取り
N,P,Q,R=map(int,input().split())
A=list(map(int,input().split()))
 
# 区間和=Pとなる区間のリスト
Plist=[]
# 区間和(初期値はA[0])
S=A[0]
 
# (1)左端=l、右端=rを0とする
# 区間の右
r=0
# l(区間の左)=0~(N-1)
for l in range(N):
 
    # (2)A[l]~A[r]について区間和を計算する
    # r<Nの間
    while r<N:
        # ・区間和がP未満ならば
        if S<P:
            # 右端=rを進める(+1する)
            r+=1
            # 右端を超えたら
            if r==N:
                # 終了
                break
            # A[r]を足す
            S+=A[r]
        # ・区間和がP以上
        else:
            # ・区間和がPならば区間を記録する
            if S==P:
                # 区間を記録
                Plist.append([l,r])
            # 左端=lを進める(+1する)
            break
   
    # 左を進めるのでマイナス
    S-=A[l]
 
 
# 区間和=Qとなる区間のリスト
Qlist=[]
 
# Plistと同様に作る
S=A[0]
r=0
for l in range(N):
    while r<N:
        if S<Q:
            r+=1
            if r==N:
                break
            S+=A[r]
        else:
            if S==Q:
                Qlist.append([l,r])
            break    
    S-=A[l]
 
# 区間和=Rとなる区間のリスト
Rlist=[]
 
# Plistと同様に作る
S=A[0]
r=0
for l in range(N):
    while r<N:
        if S<R:
            r+=1
            if r==N:
                break
            S+=A[r]
        else:
            if S==R:
                Rlist.append([l,r])
            break    
    S-=A[l]
 
# Plist,Qlist,Rlistのどれかが空なら
if len(Plist)==0 or len(Qlist)==0 or len(Rlist)==0:
    # 「No」を出力
    print("No")
    # 終了
    exit()
 
# Qlistのi2番目を確認
i2=0
# Qlistのi3番目を確認
i3=0
 
# i1=0~(Plistの長さ-1)
for i1 in range(len(Plist)):
    # Plistのi1番目の区間の右
    Pr=Plist[i1][1]
    # Qlistのi2番目の区間の左
    Ql=Qlist[i2][0]
 
    # 「Qlistの区間の左」<「Plistの区間の右」+1である間
    while Ql<Pr+1:
        # Qlistの次の区間へ進む
        i2+=1
        # i2がQlistの長さを超えたら
        if i2==len(Qlist):
            # 「No」を出力
            print("No")
            # 終了
            exit()
        # Qlistのi2番目の区間の左
        Ql=Qlist[i2][0]
 
    # 「Qlistの区間の左」<「Plistの区間の右」+1になったら
    if Ql==Pr+1:
        # Qlistのi2番目の区間の右
        Qr=Qlist[i2][1]
        # Rlistのi3番目の区間の左
        Rl=Rlist[i3][0]
 
        # 「Rlistの区間の左」<「Qlistの区間の右」+1である間
        while Rl<Qr+1:
            # Rlistの次の区間へ進む
            i3+=1
            # i2がRlistの長さを超えたら
            if i3==len(Rlist):
                # 「No」を出力
                print("No")
                # 終了
                exit()
            # Rlistのi3番目の区間の左
            Rl=Rlist[i3][0]
       
        # 「Rlistの区間の左」<「Qlistの区間の右」+1になったら
        if Rl==Qr+1:
            # 「Yes」を出力
            print("Yes")
            # 終了
            exit()
 
# 「No」を出力
print("No")

ABC266 A

# 入力の受け取り
S=input()
 
# (Sの文字数)を2で割った商
X=len(S)//2
 
# SのX文字目を出力
print(S[X])

ABC266 B

# 入力の受け取り
N=int(input())
 
# 998244353で割った余りを出力
print(N%998244353)

ABC266 C

# 入力の受け取り
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))
D=list(map(int,input().split()))
 
#点abのベクトル
def vec(a,b):
    # ベクトルを返す
    return (a[0]-b[0],a[1]-b[1])
 
#三角形abcの内部に点pがあるか確認する
# 内部ならTrueを返す
def InTrianble(a,b,c,p):
 
    # それぞれのベクトルを計算
    ab=vec(b,a)
    bp=vec(p,b)
 
    bc=vec(c,b)
    cp=vec(p,c)
 
    ca=vec(a,c)
    ap=vec(p,a)
 
    #外積(Outer Product)を求める
    OP1=ab[0]*bp[1]-ab[1]*bp[0]
    OP2=bc[0]*cp[1]-bc[1]*cp[0]
    OP3=ca[0]*ap[1]-ca[1]*ap[0]
 
    #外積の向き　正負がそろっていれば内側
    if (OP1>0 and OP2>0 and OP3>0) or (OP1<0 and OP2<0 and OP3<0):
        return True
 
# 三角形ABCの内側にDがあるか？
# 三角形BCDの内側にAがあるか？
# 三角形CDAの内側にBがあるか？
# 三角形DABの内側にCがあるか？
if InTrianble(A,B,C,D)==True or InTrianble(B,C,D,A)==True or InTrianble(C,D,A,B)==True or InTrianble(D,A,B,C)==True:
    # 「No」を出力
    print("No")
# 上記全て成り立たない
else:
    # 「Yes」を出力
    print("Yes")

ABC266 D

# 入力の受け取り
N=int(input())
 
# すぬけ君の現れる時刻、座標と大きさを記録する
Size=[[0]*5 for i in range(10**5+1)]
 
# N回
for i in range(N):
    # 入力の受け取り
    T,X,A=map(int,input().split())
    # T秒時点で座標Xに大きさAのすぬけ君が出ると記録
    Size[T][X]=A
 
# (1)表を作る
# (2)すぐにわかるところを埋める
dp=[[0]*5 for i in range(10**5+1)]
 
# (3)表の小さい方から答えにたどり着くまで埋める
# t=1~10^5
for t in range(1,10**5+1):
    # 左上、上、右上のうち一番大きいものを埋める
    dp[t][0]=max(dp[t-1][0],dp[t-1][1])
    dp[t][1]=max(dp[t-1][0],dp[t-1][1],dp[t-1][2])
    dp[t][2]=max(dp[t-1][1],dp[t-1][2],dp[t-1][3])
    dp[t][3]=max(dp[t-1][2],dp[t-1][3],dp[t-1][4])
    dp[t][4]=max(dp[t-1][3],dp[t-1][4])
 
    # x=0~4
    for x in range(5):
        # x≤tならば(時刻tに座標xへ到達できるなら)
        if x<=t:
            # すぬけ君を捕まえる
            dp[t][x]+=Size[t][x]
 
# (4)答えを出力する
# 10**5行の最大値を出力
print(max(dp[10**5]))

ABC267 A

# 入力の受け取り
S=input()
 
# S=「Monday」ならば
if S=="Monday":
    # 5を出力
    print(5)
# S=「Tuesday」ならば
elif S=="Tuesday":
    # 4を出力
    print(4)
# S=「Wednesday」ならば
elif S=="Wednesday":
    # 3を出力
    print(3)
# S=「Thursday」ならば
elif S=="Thursday":
    # 2を出力
    print(2)
# S=「Friday」ならば
elif S=="Friday":
    # 1を出力
    print(1)

ABC267 B

# 入力の受け取り
# 0文字目を「?」で埋める
S="?"+input()
 
# ピン1が倒れていなければ
if S[1]=="1":
    # 「No」を出力
    print("No")
    # 終了
    exit()
 
# どの列が倒れているかを確認
T=""
 
# ピン7が倒れていなければ⇔S[7]=「1」ならば
if S[7]=="1":
    # Tの末尾に「A」を追加
    T+="A"
# それ以外(ピン7が倒れていれば⇔S[7]=「0」ならば)
else:
    # Tの末尾に「B」を追加
    T+="B"
 
# ピン4が倒れていなければ⇔S[4]=「1」ならば
if S[4]=="1":
    # Tの末尾に「A」を追加
    T+="A"
# それ以外(ピン4が倒れていれば⇔S[4]=「0」ならば)
else:
    # Tの末尾に「B」を追加
    T+="B"
 
# ピン2 または ピン8が倒れていなければ⇔S[2]=「1」 or S[8]=「1」ならば
if S[2]=="1" or S[8]=="1":
    # Tの末尾に「A」を追加
    T+="A"
# それ以外(ピン2とピン8両方が倒れていれば⇔S[2]=「1」 and S[8]=「1」ならば)
else:
    # Tの末尾に「B」を追加
    T+="B"
 
# ピン5が倒れていなければ⇔S[5]=「1」ならば
if S[5]=="1":
    # Tの末尾に「A」を追加
    T+="A"
# それ以外(ピン5が倒れていれば⇔S[5]=「0」ならば)
else:
    # Tの末尾に「B」を追加
    T+="B"
 
# ピン3 または ピン9が倒れていなければ⇔S[3]=「1」 or S[9]=「1」ならば
if S[3]=="1" or S[9]=="1":
    # Tの末尾に「A」を追加
    T+="A"
# それ以外(ピン3とピン9両方が倒れていれば⇔S[3]=「1」 and S[9]=「1」ならば)
else:
    # Tの末尾に「B」を追加
    T+="B"
 
# ピン6が倒れていなければ⇔S[6]=「1」ならば
if S[6]=="1":
    # Tの末尾に「A」を追加
    T+="A"
# それ以外(ピン6が倒れていれば⇔S[6]=「0」ならば)
else:
    # Tの末尾に「B」を追加
    T+="B"
 
# ピン10が倒れていなければ⇔S[10]=「1」ならば
if S[10]=="1":
    # Tの末尾に「A」を追加
    T+="A"
# それ以外(ピン10が倒れていれば⇔S[10]=「0」ならば)
else:
    # Tの末尾に「B」を追加
    T+="B"
 
# 「ABA」がTにあれば
if "ABA" in T:
    # 「Yes」を出力
    print("Yes")
# 「ABBA」がTにあれば
elif "ABBA" in T:
    # 「Yes」を出力
    print("Yes")
# 「ABBBA」がTにあれば
elif "ABBBA" in T:
    # 「Yes」を出力
    print("Yes")
# 「ABBBBA」がTにあれば
elif "ABBBBA" in T:
    # 「Yes」を出力
    print("Yes")
# 「ABBBBBA」がTにあれば
elif "ABBBBBA" in T:
    # 「Yes」を出力
    print("Yes")
# それ以外
else:
    # 「No」を出力
    print("No")

ABC267 C

# 入力の受け取り
N,M=map(int,input().split())
# 0番目を[0]などてきとうな数で埋める
A=[0]+list(map(int,input().split()))
 
# 答え
ans=0
 
# i=1~M
for i in range(1,M+1):
    # i*A[i]を足す
    ans+=i*A[i]
 
# 累積和の計算
ACum=[0]*(N+1)
# i=1~N
for i in range(1,N+1):
    # 計算する
    ACum[i]=ACum[i-1]+A[i]
 
# S：「B1=Ai(B：Ai A(i+1) A(i+2) ... A(i+M-1)の場合」のΣi*Biの値
S=ans
 
# i=2~(N-M+1)
for i in range(2,N-M+2):
    # 「B1=Ai(B：Ai A(i+1) A(i+2) ... A(i+M-1))の場合」=「B1=A(i-1)(B：A(i-1) Ai A(i+1) ... A(i+M-2))の場合」-(「A(i-1)~A(i+M-2)の和」)+A(i+M-1)*M
    S=S-(ACum[i+M-2]-ACum[i-2])+A[i+M-1]*M
    # それまでの答えより大きければ更新
    ans=max(ans,S)
 
# 答えの出力
print(ans)

ABC267 D

# 入力の受け取り
N,M=map(int,input().split())
A=[0]+list(map(int,input().split()))
 
# (1)表を作る
dp=[[-10**15]*(N+1) for i in range(M+1)]
 
# (2)すぐにわかるところを埋める
# x=1~N
for x in range(1,N+1):
    dp[1][x]=A[x]
 
# (3)表の小さい方から答えにたどり着くまで埋める
# k=2~M
for k in range(2,M+1):
    # (k-1)行目の最大値
    dpMax=dp[k-1][0]
    # x=k~N
    for x in range(k,N+1):
        # (k-1)行目の最大値 dp[k-1][x-1]がそれまでの最大値より大きければ更新
        dpMax=max(dp[k-1][x-1],dpMax)
        # (2≤k,k≤x)dp[i][x]=「「(k-1)行目,(1~(x-1))列の最大値」+k*Ax
        dp[k][x]=dpMax+k*A[x]
 
# (4)答えを出力する
# M行目の最大値
print(max(dp[M]))

ABC268 A

# 入力の受け取り
A,B,C,D,E=map(int,input().split())
 
# 重複のない整数をカウント
count=1
 
# BとAが違うなら
if B!=A:
    # カウントにプラス1
    count+=1
# CとA,Bが違うなら
if C!=A and C!=B:
    # カウントにプラス1
    count+=1
# DとA,B,Cが違うなら
if D!=A and D!=B and D!=C:
    # カウントにプラス1
    count+=1
# EとA,B,C,Dが違うなら
if E!=A and E!=B and E!=C and E!=D:
    # カウントにプラス1
    count+=1
   
# カウントの値を出力
print(count)

# リストで受け取り
x=list(map(int,input().split()))
 
# セットへ変換
x=set(x)
 
# 長さを出力
print(len(x))

ABC268 B

# 入力の受け取り
S=input()
T=input()
 
# S=Tの先頭から(Sの長さ) ならば
if S==T[0:len(S)]:
    # 「Yes」を出力
    print("Yes")
# そうでなければ
else:
    # 「No」を出力
    print("No")

ABC268 C

# 入力の受け取り
N=int(input())
p=list(map(int,input().split()))
 
# 料理の場所を記録
indx=[0]*N
 
# i=0~(N-1)
for i in range(N):
    # 料理piは位置iにある
    indx[p[i]]=i
 
# 距離
dist=[0]*N
 
# i=0~(N-1)
for i in range(N):
    # 距離を計算
    dist[i]=(i-indx[i])%N
 
# 距離ごとの料理の個数
count=[0]*N
 
# i=0~(N-1)
for i in range(N):
    # 距離iの料理の個数をカウント
    count[dist[i]]+=1
 
# 答え
ans=0
 
# i=1~N
for i in range(N):
    # 距離(0,1,2)の料理の個数合計を計算(1回転によって距離(N-1,0,1)にできる)
    # 距離(1,2,3)の料理の個数合計を計算(2回転によって距離(N-1,0,1)にできる)
    # 距離(2,3,4)の料理の個数合計を計算(3回転によって距離(N-1,0,1)にできる)
    # ...
    # 距離(N-2,N-1,0)の料理の個数合計を計算((N-1)回転によって距離(N-1,0,1)にできる)
    # 距離(N-1,0,1)の料理の個数合計を計算
    # そこまでの答えより大きければ更新
    ans=max(ans,count[i]+count[(i+1)%N]+count[(i+2)%N])
 
# 答えの出力
print(ans)

ABC269 A

# 入力の受け取り
a,b,c,d=map(int,input().split())
 
# (a+b)*(c-d)を出力
print((a+b)*(c-d))
 
# 「Takahashi」を出力
print("Takahashi")

ABC269 B

# 入力の受け取りリスト
Slist=[]
 
# 10回
for i in range(10):
    # 入力の受け取り
    S=input()
    # リストへ追加
    Slist.append(S)
 
# A=0~9
for A in range(10):
    # B=A~9
    for B in range(A,10):
        # C=0~9
        for C in range(10):
            # D=C~9
            for D in range(C,10):
                # 条件を満たしている間True
                OK=True
 
                # i=0~9
                for i in range(10):
                    # j=0~9
                    for j in range(10):
                        # A≤i≤B かつ C≤j≤D の場合
                        if A<=i<=B and C<=j<=D:
                            # Siのj文字目が「.」ならば
                            if Slist[i][j]==".":
                                # 条件を満たさない
                                OK=False
                       
                        # そうでなければ
                        else:
                            # Siのj文字目が「#」ならば
                            if Slist[i][j]=="#":
                                # 条件を満たさない
                                OK=False
 
                # 条件を満たしていれば
                if OK==True:
                    # 答えの出力
                    print(A+1,B+1)
                    print(C+1,D+1)
                    # 終了
                    exit()

# 初期値
A,B=10,1
C,D=10,1
 
# i=0~9
for i in range(10):
    # 入力の受け取り
    S=input()
    # Sに"#"が含まれていれば
    if "#" in S:
        # A,Bを更新
        A=min(A,i+1)
        B=max(B,i+1)
        # j=0~9
        for j in range(10):
            # Sのj文字目が"#"ならば
            if S[j]=="#":
                # C,Dを更新
                C=min(C,j+1)
                D=max(D,j+1)
 
# 答えを出力
print(A,B)
print(C,D)

ABC269 C

# 入力の受け取り
N=int(input())
 
# Nを2進数へ変換
Nbit=bin(N)
# 「0b」を消す
Nbit=Nbit[2:]
# 反転
Nbit=Nbit[::-1]
 
# xlistへ空の文字列を入れておく
xlist=[""]
 
# i=0~(Nbitの長さ-1)まで
for i in range(len(Nbit)):
    # 新しいxlistのリスト
    Newxlist=[]
 
    # Nの右からi桁目が「0」ならば
    if Nbit[i]=="0":
        # x：xlistの要素を順に格納
        for x in xlist:
            # 先頭に「0」をつける
            Newxlist.append("0"+x)
   
    # Nの右からi桁目が「1」ならば
    else:
        # # x：xlistの要素を順に格納
        for x in xlist:
            # 先頭に「0」をつける
            Newxlist.append("0"+x)
            # 先頭に「1」をつける
            Newxlist.append("1"+x)
   
    # xlistを更新
    xlist=Newxlist
 
# xを10進数に変換した数の格納リスト
anslist=[]
 
# # x：xlistの要素を順に格納
for x in xlist:
    # 10進数へ変換して追加
    anslist.append(int(x,2))
 
# 小さい順に並び替え
anslist.sort()
 
# ans：anslistの要素を順に格納
for ans in anslist:
    # ansを10進数へ変換
    print(ans)

ABC269 D

# 入力の受け取り
N=int(input())
 
# 黒いマスの管理
Black=[[0]*3000 for i in range(3000)]
 
# スタート地点の候補
Start=[]
 
# N回
for i in range(N):
    # 入力の受け取り
    X,Y=map(int,input().split())
   
    # 0以上にするため1000プラスする
    X+=1000
    Y+=1000
    # (X,Y)が黒いマス
    Black[X][Y]=1
    # スタート地点の候補
    Start.append([X,Y])
 
# 訪問済み座標の管理
visited=[[False]*3000 for i in range(3000)]
 
# dequeを用意
from collections import deque
que=deque()
 
# 答え
ans=0
 
# (1)Startから座標を取り出す
for X,Y in Start:
    # (2)取り出した座標が訪問済みでなければキューに入れて、訪問済みにする
    if visited[X][Y]==0:
        # キューへ追加
        que.append([X,Y])
        # 訪問済みにする
        visited[X][Y]=1
        # 答えをプラス1
        ans+=1
 
        # (6)キューが空になるまで(4)を繰り返す。空になったら(1)へ戻る
        while 0<len(que):
            # (4)キューの左端から座標を取り出す(今いる座標)
            NowX,NowY=que.popleft()
 
            # (5)今いる座標から進める座標が黒マスかつ訪問済みでなければ、訪問済みにし、キューへ入れる
            if Black[NowX-1][NowY-1]==1 and visited[NowX-1][NowY-1]==0:
                # 訪問済みにする
                visited[NowX-1][NowY-1]=1
                # キューに入れる
                que.append([NowX-1,NowY-1])
            if Black[NowX-1][NowY]==1 and visited[NowX-1][NowY]==0:
                visited[NowX-1][NowY]=1
                que.append([NowX-1,NowY])
            if Black[NowX][NowY-1]==1 and visited[NowX][NowY-1]==0:
                visited[NowX][NowY-1]=1
                que.append([NowX,NowY-1])
            if Black[NowX][NowY+1]==1 and visited[NowX][NowY+1]==0:
                visited[NowX][NowY+1]=1
                que.append([NowX,NowY+1])
            if Black[NowX+1][NowY]==1 and visited[NowX+1][NowY]==0:
                visited[NowX+1][NowY]=1
                que.append([NowX+1,NowY])
            if Black[NowX+1][NowY+1]==1 and visited[NowX+1][NowY+1]==0:
                visited[NowX+1][NowY+1]=1
                que.append([NowX+1,NowY+1])
 
# 答えの出力
print(ans)

ABC269 E

# 入力の受け取り
N=int(input())
 
# 行の探索範囲
Gmin=1
Gmax=N
 
# 列の探索範囲
Rmin=1
Rmax=N
 
# 20回
for i in range(20):
 
    # 範囲の中央を確認
    Gcen=(Gmin+Gmax)//2
    Rcen=(Rmin+Rmax)//2
 
    # Gmin~Gcenの個数を確認
    print("?",Gmin,Gcen,1,N)
    T=int(input())
 
    # 答えが(Gcen-Gmin+1)より小さいならば
    if T<Gcen-Gmin+1:
        # Gmin~Gcen行目のどこかに置ける
        Gmax=Gcen
    # それ以外(答えが(Gcen-Gmin+1)ならば)
    else:
        # (Gcen+1)~Gmax行目のどこかに置ける
        Gmin=Gcen+1
   
    # 列も同様
    print("?",1,N,Rmin,Rcen)
    T=int(input())
 
    if T<Rcen-Rmin+1:
        Rmax=Rcen
    else:
        Rmin=Rcen+1
 
    # 行、列の範囲が定まったら
    if Gmin==Gmax and Rmin==Rmax:
        # 答えの出力
        print("!",Gmin,Rmin)
        # 終了
        exit()

ABC270 A

# 入力の受け取り
A,B=map(int,input().split())
 
# 1点問題が解けたら=1
X=0
# 2点問題が解けたら=1
Y=0
# 4点問題が解けたら=1
Z=0
 
# A=1ならば
if A==1:
    # X=1にする
    X=1
elif A==2:
    Y=1
elif A==3:
    X=1
    Y=1
elif A==4:
    Z=1
elif A==5:
    X=1
    Z=1
elif A==6:
    Y=1
    Z=1
elif A==7:
    X=1
    Y=1
    Z=1
 
# Bも同様
if B==1:
    X=1
elif B==2:
    Y=1
elif B==3:
    X=1
    Y=1
elif B==4:
    Z=1
elif B==5:
    X=1
    Z=1
elif B==6:
    Y=1
    Z=1
elif B==7:
    X=1
    Y=1
    Z=1
 
# 答え
ans=0
 
# 1点問題が解けていたら
if X==1:
    # 答えにプラス1
    ans+=1
# 2点問題が解けていたら
if Y==1:
    # 答えにプラス2
    ans+=2
# 4点問題が解けていたら
if Z==1:
    # 答えにプラス4
    ans+=4
 
# 答えの出力
print(ans)

# 入力の受け取り
A,B=map(int,input().split())
 
# AorBを計算
print(A|B)

ABC270 B

# 入力の受け取り
X,Y,Z=map(int,input().split())
 
# -1になるパターン
if 0<Y<X<Z or 0<Y<Z<X or X<Z<Y<0 or Z<X<Y<0:
    # -1を出力
    print(-1)
# 2|Z|+|X|になるパターン
elif X<Y<0<Z or Z<0<Y<X:
    # 2|Z|+|X|を出力
    print(2*abs(Z)+abs(X))
# それ以外
else:
    # |X|を出力
    print(abs(X))

ABC270 C

# 入力の受け取り
N,X,Y=map(int,input().split())
 
# 繋がっている頂点の記録
# connect[1]=[2,3,4]なら頂点1から頂点2,3,4へ行ける
connect=[[] for i in range(N+1)]
 
# (N-1)回
for i in range(N-1):
    # 入力の受け取り
    U,V=map(int,input().split())
    # 繋がっている頂点の記録
    connect[U].append(V)
    connect[V].append(U)
 
# 頂点Xからの距離(初期値は-1)
Dist=[-1]*(N+1)
# 頂点Xの距離は0
Dist[X]=0
 
# キューを用意
# インポート
from collections import deque
que=deque()
 
# (1)Xをキューへ追加
que.append(X)
 
# (4)キューが空になるまで(2)~(3)を繰り返す
while 0<len(que):
    # (2)キューの左端(先頭)から頂点を取り出す(今いる頂点)
    Now=que.popleft()
 
    # (3)今いる頂点から行ける頂点について
    # to：今いる頂点から行ける頂点
    for to in connect[Now]:
        # ・距離が更新されていないならば(まだ到達していない頂点ならば)
        if Dist[to]==-1:
            # 距離を記録(今いる頂点の距離+1)
            Dist[to]=Dist[Now]+1
            # キューへ追加
            que.append(to)
 
# 答え
ans=deque()
 
# 頂点Yの距離
Count=Dist[Y]
 
# 今いる頂点
Now=Y
 
# Countが1以上の間
while 0<Count:
    # 答えの左端(先頭)に今いる頂点を追加
    ans.appendleft(Now)
 
    # 今いる頂点から行ける頂点
    for to in connect[Now]:
        # 距離が(Count-1)である頂点を見つけたら
        if Dist[to]==Count-1:
            # Countをマイナス1
            Count-=1
            # その頂点へ移動
            Now=to
 
# 答えの先頭にXを追加
ans.appendleft(X)
 
# 答えの出力(*をつけるとカッコなしで出力できる)
print(*ans)