ARC119～128,UnionFind,FenwickTree 『 AtCoder ABC201～225 ARC119～128 灰・茶・緑問題 超詳細解説』コピペ用コード

ABC201~210
https://qiita.com/sano192/items/2efd871a4b2dee05c321

ABC211~220
https://qiita.com/sano192/items/03c27d4316af25bdf645

ABC220~225
https://qiita.com/sano192/items/8fe5e85a5b3fb15bb49b

# ARC119 A
https://atcoder.jp/contests/arc119/tasks/arc119_a

```python:提出
# 入力の受け取り
N=int(input())

# 「暫定答え」
ans=10**20

# b=0~59
for b in range(60):
    # aを計算
    a=N//2**b
    # cを計算
    c=N-a*2**b
    # 「暫定答え」より「a+b+c」が小さければ更新
    ans=min(ans,a+b+c)

# 答えを出力
print(ans)
```

# ARC119 B
https://atcoder.jp/contests/arc119/tasks/arc119_b

```python:提出
# 入力の受け取り
N=int(input())
S=input()
T=input()

# 「0」の個数が不一致なら
if S.count("0")!=T.count("0"):
    # 「-1」を出力
    print(-1)
    # 終了
    exit()

# 「0」がある場所
S_0=[]
T_0=[]

# i=0~(N-1)
for i in range(N):
    # 「0」の位置を記録
    if S[i]=="0":
        S_0.append(i)
    if T[i]=="0":
        T_0.append(i)

# 答え
ans=0

# i=0~(S_0の長さ)
for i in range(len(S_0)):
    # 一致しないなら
    if S_0[i]!=T_0[i]:
        # 答えにカウント
        ans+=1

# 答えを出力
print(ans)
```

# ARC120 A
https://atcoder.jp/contests/arc120/tasks/arc120_a

```python:提出
# 入力の受け取り
N=int(input())
A=list(map(int,input().split()))

# Aの累積和
A_cum=[0]*N
# 最初にA[0]を入れておく
A_cum[0]=A[0]

# i=1~(N-1)
for i in range(1,N):
    # 「iまでの累積和」=「(i-1)までの累積和」+A[i]
    A_cum[i]=A_cum[i-1]+A[i]

# 最大値
m=0
# fの値
f=0

# k=1~(N-1)
for k in range(N):
    # k番目までの最大値
    # そこまでの最大値よりA[k]が大きければ更新
    m=max(m,A[k])

    # f+(k+1)*m+「kまでの累積和」
    f+=(k+1)*m+A_cum[k]
    # 出力
    print(f)
    # (k+1)*mを引いておく
    f-=(k+1)*m
```

# ARC120 B
https://atcoder.jp/contests/arc120/tasks/arc120_b

```python:提出
# 余りの定義
mod=998244353

# 入力の受け取り
H,W=map(int,input().split())

# マス目の記録用リスト
grid=[]
# H回
for i in range(H):
    # 受け取り
    S=input()
    # 1文字ずつリストへ展開
    S_list=list(S)
    # gridへ記録
    grid.append(S_list)

# 距離ごとのマス目の種類を記録するセット
dist=[set() for i in range(H+W)]

# gyou=0~(H-1)
for gyou in range(H):
    # retu=0~(W-1)
    for retu in range(W):
        # 距離=行番号+列番号
        dist[gyou+retu].add(grid[gyou][retu])

# 答え
ans=1

# i=0~(H+W)
for i in range(H+W):
    # (3)赤と青が混在
    if "R" in dist[i] and "B" in dist[i]:
        # 「0」を出力
        print(0)
        # 終了
        exit()

    # (1)全部色が塗られていないマス=全マスが「.」の場合
    elif dist[i]=={"."}:
        # 赤か青に統一するから2通り
        ans*=2
        # 余りを取る
        ans%=mod

# 答えの出力
print(ans)
```

# ARC121 A
https://atcoder.jp/contests/arc121/tasks/arc121_a

```python:提出
# 入力の受け取り
N=int(input())
# 座標の格納用
p=[]

# x座標と家の番号の格納用
px=[]
# y座標と家の番号の格納用
py=[]

# N回
for i in range(N):
    # 入力の受け取り
    x,y=map(int,input().split())
    # 座標を記録
    p.append([x,y])
    # x座標と家の番号を記録
    px.append([x,i])
    # y座標と家の番号を記録
    py.append([y,i])

# チェビシェフ距離の計算
# 引数：p1=[p1のx座標,p1のy座標],p2=[p2のx座標,p2のy座標] → 返り値：チェビシェフ距離
def chebyshev(p1,p2):
    return max(abs(p1[0]-p2[0]),abs(p1[1]-p2[1]))

# xの小さい順ソート
px.sort()
# yの小さい順ソート
py.sort()

# 候補となる家の番号格納用
# 重複を避けるためセット
indx=set()

# x座標が1番小さい家の番号
indx.add(px[0][1])
# x座標が2番目に小さい家の番号
indx.add(px[1][1])
# x座標が1番大きい家の番号
indx.add(px[-1][1])
# x座標が2番目に大きい家の番号
indx.add(px[-2][1])
# y座標が1番小さい家の番号
indx.add(py[0][1])
# y座標が2番目に小さい家の番号
indx.add(py[1][1])
# y座標が1番大きい家の番号
indx.add(py[-1][1])
# y座標が2番目に大きい家の番号
indx.add(py[-2][1])

# リストへ変換
indx=list(indx)

# 各家の距離記録用
dist=[]

# i=0~(indxの長さ-1)
for i in range(len(indx)):
    # j=(i+1)~(indxの長さ-1)
    for j in range(i+1,len(indx)):
        # チェビシェフ距離を計算
        d=chebyshev(p[indx[i]],p[indx[j]])
        # 距離を記録
        dist.append(d)

# 降順ソート
dist.sort(reverse=True)
# 2番目を出力
print(dist[1])
```

# ARC121 B
https://atcoder.jp/contests/arc121/tasks/arc121_b

```python:提出
# 入力の受け取り
N=int(input())

# R,G,Bをグループ分け
R=[]
G=[]
B=[]

# 2N回
for i in range(2*N):
    # 受け取り(文字列)
    a,c=map(str,input().split())
    # 割り振り
    if c=="R":
        R.append(int(a))
    elif c=="G":
        G.append(int(a))
    else:
        B.append(int(a))

# 全てのグループが偶数匹なら
if len(R)%2==0 and len(G)%2==0 and len(B)%2==0:
    # 答えは「0」
    print(0)
    exit()

# even：偶数匹グループ
# odd1,odd2：奇数匹グループ
# Rが偶数匹グループ
if len(R)%2==0:
    even,odd1,odd2=R,G,B
# Gが偶数匹グループ
elif len(G)%2==0:
    even,odd1,odd2=G,R,B
# Bが偶数匹グループ
else:
    even,odd1,odd2=B,R,G

# リストの要素について、差の絶対値の最小を計算する関数
# 引数：X.Y(リスト) → 返り値：差の絶対値の最小
def min_d(X,Y):
    # ソート
    X.sort()
    Y.sort()
    # 差(difference)
    d=10**20
    # Xのインデックス
    i=0
    # Yのインデックス
    j=0

    # i,jが範囲外にならない限り
    while i<len(X) and j<len(Y):
        # 差の絶対値を計算し、小さければ更新
        d=min(d,abs(Y[j]-X[i]))
        # 小さい方のインデックスを進める
        if X[i]<Y[j]:
            i+=1
        elif Y[j]<X[i]:
            j+=1
        # X[i]=Y[j]なら差は0
        else:
            return 0
   
    # 差の絶対値の最小を返す
    return d

# (1)2匹を一緒に住まわせる
ans=min_d(odd1,odd2)
# (2)さらに偶数匹グループから2匹取り出してそれぞれと住まわせる。
ans=min(ans,min_d(odd1,even)+min_d(odd2,even))

# 答えの出力
print(ans)
```

# ARC122 A
https://atcoder.jp/contests/arc122/tasks/arc122_a

```python:提出
# 余りを定義
mod=10**9+7

# 入力の受け取り
N=int(input())
A=list(map(int,input().split()))

# 樹形図における「i列目の「+」の個数」
Plus=[0]*(10**5+10)
# 樹形図における「i列目の「-」の個数」
Minus=[0]*(10**5+10)

# 0列目の「+」の個数=1
Plus[0]=1
# 0列目の「-」の個数=0
Minus[0]=0

# i=0~(10^5+9)
for i in range(1,10**5+10):
    # 漸化式のとおりに計算
    Plus[i]=Plus[i-1]+Minus[i-1]
    Minus[i]=Plus[i-1]
    # 余りを取る
    Plus[i]%=mod
    Minus[i]%=mod

# 「「+」をスタートとして、x列分進んだときの場合の数」
countPlus=[0]*(10**5+10)
# 初期値
countPlus[0]=1
countPlus[1]=2

# x=0~(10^5+9)
for x in range(2,10**5+10):
    # 漸化式のとおりに計算
    countPlus[x]=countPlus[x-2]+countPlus[x-1]
    # 余りを取る
    countPlus[x]%=mod

# 「「-」をスタートとして、x列分進んだときの場合の数」
countMinus=[0]*(10**5+10)
# 初期値
countMinus[0]=1
countMinus[1]=1

# x=0~(10^5+9)
for x in range(2,10**5+10):
    # 漸化式
    countMinus[x]=countMinus[x-2]+countMinus[x-1]
    # 余りを取る
    countMinus[x]%=mod

# 答え
ans=0

# i=0~(N-1)
for i in range(N):
    # +A[i]の係数：「i列目の「+」の個数」*「「+」をスタートとして、((N-1)-i)列分進んだときの場合の数」
    ans+=A[i]*Plus[i]*(countPlus[(N-1)-i])
    # -A[i]の係数：「i列目の「-」の個数」*「「-」をスタートとして、((N-1)-i)列分進んだときの場合の数」
    ans-=A[i]*Minus[i]*(countMinus[(N-1)-i])
    # 余りを取る
    ans%=mod

# 答えの出力
print(ans)
```

```python:別解
# 余りを定義
mod=10**9+7

# 入力の受け取り
N=int(input())
A=list(map(int,input().split()))

# フィボナッチ数列の計算
F=[0,1]
for i in range(2,10**5+10):
    F.append((F[i-2]+F[i-1]%mod))

# 答え
ans=0

# i=0~(N-1)
for i in range(N):
    # +A[i]の係数
    ans+=A[i]*F[i+1]*(F[(N+1)-i])
    # -A[i]の係数：
    ans-=A[i]*F[i]*(F[N-i])
    # 余りを取る
    ans%=mod

# 答えの出力
print(ans)
```

# ARC122 B
https://atcoder.jp/contests/arc122/tasks/arc122_b

```python:提出
# pypyで提出

# 入力の受け取り
N=int(input())
A=list(map(int,input().split()))

# 期待値計算
# 引数：x →　返り値：x円支払い失う金額の期待値
def E(x):
    # 期待値
    result=0
    # i=0~(N-1)まで
    for i in range(N):
        # シナリオA[i]が起きた時失う金額
        result+=(x+A[i]-min(A[i],2*x))
    # 各シナリオの起こる確率=(1/N)を掛ける⇔Nで割る
    result/=N
    # 値を返す
    return result

# 左端
L=0
# 右端
R=max(A)

# 100回
for i in range(100):
    # 中央左側
    cl=(2*L+R)/3
    # 中央右側
    cr=(L+2*R)/3
    # 中央左側が低いまたは同じ
    if E(cl)<=E(cr):
        # 右側を更新
        R=cr
    # 中央右側が低い
    else:
        # 左側を更新
        L=cl

# 答えの出力
print(E(cl))
```

```python:別解
# 入力の受け取り
N=int(input())
A=list(map(int, input().split()))

# 中央値の計算
from statistics import median
x=median(A)

# xを2で割る
x/=2

# 期待値計算
ans=0
for a in A:
    ans+=x+a-min(a,2*x)
ans/=N

# 答えの出力
print(ans)
```

# ARC123 A
https://atcoder.jp/contests/arc123/tasks/arc123_a

```python:提出
# 入力の受け取り
A1,A2,A3=map(int,input().split())

# x,yを計算
x=A2-A1
y=A3-A2

# ・x<y
if x<y:
    # x,yの偶奇が同じ
    if x%2==y%2:
        # 「A2に1加える」を((y-x)/2)回
        print((y-x)//2)
    # x,yの偶奇が違う
    else:
        # count：操作回数
        # 「A3に1加える」を1回
        count=1
        # 「A3に1加える」⇔yに+1
        y+=1
        # 「A2に1加える」を((y-x)/2)回
        count+=(y-x)//2
        # 操作回数を出力
        print(count)

# ・x=y
elif x==y:
    # 操作は不要
    print(0)

# ・y<x
else:
    # 「A3に1加える」を(x-y)回
    print(x-y)
```

# ARC123 B
https://atcoder.jp/contests/arc123/tasks/arc123_b

```python:提出
# 入力の受け取り
N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))

# 小さい順に並び替える
A.sort()
B.sort()
C.sort()

# 条件を満たす組み合わせのカウント
count=0
# 初期値
i,j,k=0,0,0

# インデックスの範囲内の間
while i<N and j<N and k<N:
    # B[j]≤A[i]なら
    if B[j]<=A[i]:
        # 次のjへ
        j+=1
    # A[i]<B[j]なら
    else:
        # C[k]≤B[j]なら
        if C[k]<=B[j]:
            # 次のkへ
            k+=1
        # B[j]<C[k]なら
        else:
            # カウントする
            count+=1
            # 次のi,j,kへ
            i+=1
            j+=1
            k+=1

# 答えの出力
print(count)
```

# ARC124 A
https://atcoder.jp/contests/arc124/tasks/arc124_a

```python:提出
# 余りの定義
mod=998244353

# 入力の受け取り
N,K=map(int,input().split())

# 各カードに書ける整数の種類数
# 最初は全てのカードに「1」「2」...「K」のK種類が書ける
cards=[K]*(N+1)

# i=1~N
for i in range(1,K+1):
    # 入力を文字列で受け取り
    c,k=map(str,input().split())
    # kを整数へ変換
    k=int(k)
 
    # k番目のカードには「i」しか書けない
    cards[k]=1

    # i=1~(N-1)
    for i in range(1,N):
        # c=「R」
        if c=="R":
            # (k+i)<(N+1)未満なら(インデックスの範囲外でなければ)
            if k+i<N+1:
                # cards[k+i]が1でなければ
                if 1!=cards[k+i]:
                    # 「i」が書けなくなる⇔書ける種類が一つ減る
                    cards[k+i]-=1
            # (k+i)=(N+1)なら
            else:
                # 次のiへ
                break
        # c=「L」
        else:
            # 0<(k-i)なら
            if 0<k-i:
                # cards[k-i]が1でなければ
                if 1!=cards[k-i]:
                    # 「i」が書けなくなる⇔書ける種類が一つ減る
                    cards[k-i]-=1
            # (k-i)=0なら
            else:
                # 次のiへ
                break

# 答え
ans=1

# i=1~N
for i in range(1,N+1):
    # 各カードに書ける種類の数を掛ける
    ans*=cards[i]
    # 余りを取る
    ans%=mod

# 答えの出力
print(ans)
```

# ARC124 B
https://atcoder.jp/contests/arc124/tasks/arc124_b

```python:提出
# 入力の受け取り
N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))

# Bをソート
B.sort()

# 答えの格納(重複除去のためセット)
ans=set()

# i=0~(N-1)
for i in range(N):
    # 答えの候補=x
    x=A[0]^B[i]

    # 計算結果を格納するリスト
    C=[]

    # i=0~(N-1)
    for i in range(N):
        # 計算結果を格納
        C.append(A[i]^x)

    # ソート(Bと一致するか確認のため)
    C.sort()
 
    # BとCが一致するなら
    if B==C:
        # 答え
        ans.add(x)

# ソートのためリストへ
ans=list(ans)
# ソート
ans.sort()

# 答えを出力
print(len(ans))
for x in ans:
    print(x)
```

# ARC125 A
https://atcoder.jp/contests/arc125/tasks/arc125_a

```python:提出
# 入力の受け取り
N,M=map(int,input().split())
S=list(map(int,input().split()))
T=list(map(int,input().split()))

# 「0」がTにあるかつ「0」がSにない
if 0 in T and 0 not in S:
    # 一致させることが不可能
    print(-1)
    # 終了
    exit()
# 「1」がTにあるかつ「1」がSにない
if 1 in T and 1 not in S:
    # 一致させることが不可能
    print(-1)
    # 終了
    exit()

# 操作回数
count=0

# 「今先頭に来ている要素」のインデックス番号
# 最初は0
now=0

# j<Mの間
for j in range(M):
    # ・「今先頭に来ている要素」=T[j]
    # S[now]＝T[i]なら
    if S[now]==T[j]:
        # 「bへ追加」
        count+=1
        # 次のjへ
        continue
   
    # ・「今先頭に来ている要素」≠T[j]    
    # i=1~N
    for i in range(1,N+1):
        # 左にi回シフトしてT[i]と一致したら
        if S[(now+i)%N]==T[j]:
            # 「左へのシフト」をi回
            count+=i
            # 「bへ追加」
            count+=1
            # 「今先頭に来ている要素」のインデックス番号
            now=(now+i)%N
            # 次のjへ
            break
 
        # i回右シフト⇔S[now]から左にi移動してT[i]と一致したら
        elif S[(now-i)%N]==T[j]:
            # 「右へのシフト」をi回
            count+=i
            # 「bへ追加」
            count+=1
            # 「今先頭に来ている要素」のインデックス番号
            now=(now-i)%N
            # 次のjへ
            break

# 答えの出力
print(count)
```

# ARC126 A
https://atcoder.jp/contests/arc126/tasks/arc126_a

```python:提出
# 入力の受け取り
T=int(input())

# T回
for i in range(T):
    # 入力の受け取り
    N2,N3,N4=map(int,input().split())

    # 答え
    ans=0

    # (1)3*2本,4*1本
    # 「10」を作った本数
    count=min(N3//2,N4)
    # 答えに加算
    ans+=count
    # 使った本数をマイナス
    N3-=count*2
    N4-=count

    # (2)3*2本,2*2本
    count=min(N3//2,N2//2)
    ans+=count
    N2-=count*2

    # (3)2*1本,4*2本
    count=min(N2,N4//2)
    ans+=count
    N2-=count
    N4-=count*2

    # (4)2*3本,4*1本
    count=min(N2//3,N4)
    ans+=count
    N2-=count*3
    N4-=count

    # (5)2*5本
    count=N2//5
    ans+=count
    print(ans)
```

# ARC127 A
https://atcoder.jp/contests/arc127/tasks/arc127_a

```python:提出
# Nを文字列で受け取り
N=input()
# Nの桁数
Nd=len(N)
# 整数へ変換
N=int(N)

# 答え
ans=0

# 『(xの桁数)<(Nの桁数)の場合』
# xの桁数：d=1~((Nの桁数)-1)
for d in range(1,Nd):
    # 先頭に並ぶ1の個数：num=1~(xの桁数)
    for num in range(1,d+1):
        # ・(先頭に並ぶ1の個数)<(xの桁数)の場合(=11○△△)
        if num<d:
            # 場合の数：9*10^((xの桁数)-(先頭に並ぶ1の個数)-1)
            count=9*10**(d-num-1)
        # ・(先頭に並ぶ1の個数)=(xの桁数)の場合(=11111)
        else:
            # 場合の数：1
            count=1
        # 合計：(場合の数)*(先頭に並ぶ1の個数)
        ans+=num*count

# 『(xの桁数)=(Nの桁数)の場合』
# 先頭に並ぶ1の個数：num=1~(Nの桁数)
for num in range(1,Nd+1):
    # (先頭に並ぶ1の個数)=numのうち最小の数≤N
    # ⇔(「1」がnum個と、後ろに「0」を並べた数)≤N
    if int("1"*num+"0"*(Nd-num))<=N:
        # 場合の数
        count=0
 
        # (1)(先頭に並ぶ1の個数)=(Nの桁数)
        # 例：11111
        if num==Nd:
            # (「1」がnum個並んだ数)≤N
            if int("1"*num)<=N:
                # 場合の数=1
                count=1
 
        # (2)(先頭に並ぶ1の個数)=((Nの桁数)-1)
        # 例：1111○
        elif num==Nd-1:
            # maru：○の値
            for maru in (0,2,3,4,5,6,7,8,9):
                # (「1」がnum個と、「maru」をつけた数)≤N
                if int("1"*num+str(maru))<=N:
                    # 場合の数プラス1
                    count+=1

        # (3)(先頭に並ぶ1の個数)≤((Nの桁数)-2)
        # 例：1○△△△,11○△△,111○△
        else:
            # maru：○の値
            for maru in (0,2,3,4,5,6,7,8,9):
                # (「1」がnum個、「maru」、残りが「9」)≤N
                if int("1"*num+str(maru)+"9"*(Nd-num-1))<=N:
                    # 場合の数：それぞれの△には0~9(10通り)の任意の数が入る
                    count+=10**(Nd-num-1)
                # (「1」がnum個、「maru」、残りが「0」)≤N
                elif int("1"*num+str(maru)+"0"*(Nd-num-1))<=N:
                    # Nを文字列へ
                    N=str(N)
                    # Nの下(△の個数)桁+1
                    count+=int(N[num+1:])+1
                    # Nを整数へ戻す
                    N=int(N)              
       
        # 合計：(場合の数)*(先頭に並ぶ1の個数)
        ans+=num*count

# 答えの出力
print(ans)
```

# ARC128 A
https://atcoder.jp/contests/arc128/tasks/arc128_a

```python:提出
# 入力の受け取り
N=int(input())
A=list(map(int,input().split()))

# 行動
v=[0]*N

# i=0~(N-2)
for i in range(N-1):
    # 金安銀高になるなら
    if A[i+1]<A[i]:
        # 今日の夜：金を売って銀を買う
        # その日の売買が1回なら
        if v[i]==0:
        # 「1」を記録
            v[i]=1
        # その日の売買が2回なら
        else:
            # 「0」を記録
            v[i]=0
 
        # 明日の朝：銀を売って金を買う
        v[i+1]=1

print(*v)
```

# ARC128 B
https://atcoder.jp/contests/arc128/tasks/arc128_b

```python:提出
# 入力の受け取り
T=int(input())

# T回
for i in range(T):
    # 入力の受け取り
    R,G,B=map(int,input().split())

    # R≤G≤Bとなるように数字を入れ替える
    # リストへ格納
    tmp=[R,G,B]
    # 小さい順に並び替え
    tmp.sort()
    # 格納し直し
    R=tmp[0]
    G=tmp[1]
    B=tmp[2]

    # 答え　初期値はバカでかい値にしておく
    ans=10**15

    # 「RとG」
    # 差が3の倍数なら
    if (G-R)%3==0:
        # 操作回数=(G-R)/3
        tmp_ans=(G-R)//3
        # R,Gの値は(G-操作回数)
        # R=G=0にする
        tmp_ans+=G-tmp_ans
        # 答えを更新
        ans=min(ans,tmp_ans)
    # 「GとB」
    # 差が3の倍数なら
    if (B-G)%3==0:
        # 操作回数=(B-G)/3
        tmp_ans=(B-G)//3
        # G,Bの値は(B-操作回数)
        # G=B=0にする
        tmp_ans+=B-tmp_ans
        ans=min(ans,tmp_ans)
  
    # 「BとR」
    # 差が3の倍数なら
    if (B-R)%3==0:
        # 操作回数=(B-R)/3
        tmp_ans=(B-R)//3
        # R,Bの値は(B-操作回数)
        # R=B=0にする
        tmp_ans+=B-tmp_ans
        # 答えを更新
        ans=min(ans,tmp_ans)  
   
    # もし答えが更新されていなければ
    if ans==10**15:
        # 「-1」を出力
        print(-1)
    # そうでなければ
    else:
        # 答えを出力
        print(ans)
```

```python:別解
# 操作回数を計算する関数
# 引数：操作する色の組　→　返り値：操作回数(同じ数に出来ないなら10^15)
def count(X,Y):
    # |X-Y|=差が3の倍数なら
    if abs(X-Y)%3==0:
        # 操作回数
        result=abs(X-Y)//3
        result+=max(X,Y)-result
        # 操作回数を返す
        return result
    # そうでなければ(差が3の倍数でない)
    else:
        # 10^15を返す
        return 10**15

# 入力の受け取り
T=int(input())

# T回
for i in range(T):
    # 入力の受け取り
    R,G,B=map(int,input().split())
 
    # 答え初期値はバカでかい値にしておく
    ans=10**15

    # それぞれの組み合わせについて操作回数を計算
    ans=min(ans,count(R,G))
    ans=min(ans,count(G,B))
    ans=min(ans,count(B,R))
   
    # もし答えが更新されていなければ
    if ans==10**15:
        # 「-1」を出力
        print(-1)
    # そうでなければ
    else:
        # 答えを出力
        print(ans)
```

# クラス解説：UnionFind

```python:全体
# 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)

    # size(a)：aが属する木の要素数
    # 引数：a　→　返り値：aが属する木の要素数
    def size(self,a):
        # 根の絶対値(=要素数)を返す
        return abs(self.parent_size[self.leader(a)])

    # groups()：それぞれの木の内容を二次元配列として返す
    # 引数：なし　→　返り値：木の内容
    def groups(self):
        # グループの格納リストを作る
        result=[[] for _ in range(self.N)]
        # リストの生成
        for i in range(self.N):
            result[self.leader(i)].append(i)
        # 空の要素を消す
        return [r for r in result if r!=[]]
```

# クラス解説：FenwickTree

```python:全体
# 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)
```