# TTPC2022

例：

Python

import sys
N = int(sys.stdin.readline())
print("N =", N)
S = sys.stdin.readline().rstrip()
print("S =", S)

C++

#include<iostream>
#include<string>
using namespace std;

int main(){
    int N;
    string S;
    cin >> N >> S;
    cout << "N = " << N << "\nS = " << S << '\n';
}

## A
担当：nickname

from math import gcd
x, y = map(int, input().split())
d = gcd(x-2015, y-x)
ans = set()
for i in range(1, d+1):
    if i*i > d: break
    if d%i == 0: ans.add(i); ans.add(d//i)
print(*sorted(ans), sep="\n")

## B
担当：ぽんた

#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rrep(i, n) for (int i = (int)(n)-1; i >= 0; --i)
#define rep2(i, a, b) for (int i = (int)a; i < (int)(b); ++i)
#define rrep2(i, a, b) for (int i = (int)(b)-1; i >= (int)(a); --i)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
constexpr int MAX_N = 10000;

int main(){
    int N, X;
    scanf("%d %d", &N, &X);
    int dp[2][MAX_N];
    memset(dp,-1,sizeof dp);
    string now = to_string(X);
    sort(now.begin(), now.end());
    do{
        dp[0][stoi(now)] = 0;
    }while(next_permutation(now.begin(), now.end()));
    rep(i, N){
        int A;
        scanf("%d", &A);
        rep(j, MAX_N) dp[(i^1)&1][j] = dp[i&1][j];
        rep2(j, A, MAX_N) if(dp[i&1][j] >= 0){
            int left = j - A;
            string now = to_string(left);
            sort(now.begin(), now.end());
            do{
                chmax(dp[(i^1)&1][stoi(now)], dp[i&1][j]+1);
            }while(next_permutation(now.begin(), now.end()));
        }
    }
    printf("%d\n", *max_element(dp[N&1],dp[N&1] + MAX_N));
    return 0;
}

## C
担当：Shiro

import random
import sys
input = lambda: sys.stdin.readline().rstrip()
ii = lambda: int(input())
mi = lambda: map(int, input().split())
li = lambda: list(mi())
inf = 2 ** 63 - 1
mod = 998244353
from bisect import bisect_left, bisect_right
import itertools

n = 100000

a = [[random.randint(0, 998244353) for _ in range(n)] for _ in range(5)]

for i in range(5):
    a[i].sort()


ans = 0
for x in range(5):
    c = a[x]
    s = [0, 1, 2, 3, 4]
    s.remove(x)
    for i in range(n):
        le = [0] * 5
        lt = [0] * 5
        ge = [0] * 5
        gt = [0] * 5
        for now in range(5):
            le[now] = bisect_right(a[now], c[i])
            lt[now] = bisect_left(a[now], c[i])
            ge[now] = n - le[now]
            gt[now] = n - lt[now]
        cnt = 1
        for v in itertools.combinations(s, 2):
            for now in range(5):
                if now in v:
                    if x < now:
                        cnt *= le[now]
                    else:
                        cnt *= lt[now]
                elif now != x:
                    if x < now:
                        cnt *= ge[now]
                    else:
                        cnt *= gt[now]
                cnt %= mod
            ans += c[i] * cnt
        ans %= mod
print(ans)

## D
担当：nick、ぽんた
木DPでいけそう。持つ情報は[頂点が反転されているか][部分木で黒で塗られている頂点数]

#include<cstdio>
#include<vector>
#include<stack>
#include<cstring>
using namespace std;

int main(){
    int N;
    scanf("%d", &N);
    int A[N];
    for(int i = 0; i < N; ++i) scanf("%d", A + i);
    vector<int> adj[N];
    for(int i = 1; i < N; ++i){
        int tmp1, tmp2;
        scanf("%d %d", &tmp1, &tmp2);
        --tmp1;--tmp2;
        adj[tmp1].push_back(tmp2);
        adj[tmp2].push_back(tmp1);
    }
    int dp[N][2];
    memset(dp,0,sizeof dp);
    bool has_been_discovered[N], has_been_exited[N], has_child[N];
    memset(has_been_discovered, 0, sizeof has_been_discovered);
    memset(has_been_exited, 0, sizeof has_been_exited);
    memset(has_child, 0, sizeof has_child);
    stack<int> stk;
    stk.push(0);
    while(!stk.empty()){
        int u = stk.top(); stk.pop();
        if(has_been_discovered[u]){
            if(has_child[u]) dp[u][1] = -500;
            for(auto i : adj[u]){
                if(has_been_exited[i]){
                    //現在注目している頂点の親はdpの更新式に入れない
                    //dpの更新式
                    int tmp[2];
                    tmp[0] = max(dp[i][0] + dp[u][0], dp[i][1] + dp[u][1]);
                    tmp[1] = max(dp[i][1] + dp[u][0], dp[i][0] + dp[u][1]);
                    dp[u][0] = tmp[0];
                    dp[u][1] = tmp[1];
                }
            }
            ++dp[u][A[u]^1];
            has_been_exited[u] = true;
        }else{
            has_been_discovered[u] = true;
            stk.push(u);
            for (auto i : adj[u]){
                if(!has_been_discovered[i]){
                    has_child[u] = true;
                    stk.push(i);
                }
            }
        }
    }
    printf("%d\n", max(dp[0][0], dp[0][1]));
    return 0;
}

## E
担当：shiro
部分点解法を書きます
文字列A+Bを考えて、前後から交互に貪欲に取っていく
部分点もらえました

#include<iostream>
#include<string>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rrep(i, n) for (int i = (int)(n)-1; i >= 0; --i)
#define rep2(i, a, b) for (int i = (int)a; i < (int)(b); ++i)
#define rrep2(i, a, b) for (int i = (int)(b)-1; i >= (int)(a); --i)
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
int main(){
    cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    string A, B;
    getline(cin, A);
    getline(cin, B);
    int len_A = A.length(), len_B = B.length();
    int next_A[len_A][53], next_B[len_B][53];
    auto char_to_idx = [](char x){
        if(x < 'A') return 52;
        else return x <= 'Z' ? x - 'A' : 26 + (x - 'a');
    };
    fill(next_A[len_A-1], next_A[len_A-1]+53, -1);
    next_A[len_A-1][char_to_idx(A[len_A-1])] = len_A-1;
    rrep(i, len_A-1){
        copy(next_A[i+1], next_A[i+1]+53, next_A[i]);
        next_A[i][char_to_idx(A[i])] = i;
    }
    fill(next_B[0], next_B[0]+53, -1);
    next_B[0][char_to_idx(B[0])] = 0;
    rep(i, len_B-1){
        copy(next_B[i], next_B[i]+53, next_B[i+1]);
        next_B[i+1][char_to_idx(B[i+1])] = i+1;
    }
    int Q;
    cin >> Q;
    cin.ignore();
    rep(_,Q){
        string S;
        getline(cin, S);
        int ok_A = 0;
        int now = 0;
        int len_S = S.length();
        while(ok_A < len_S){
            now = next_A[now][char_to_idx(S[ok_A])]+1;
            if(!now) break;
            ++ok_A;
            if(now == len_A || ok_A == len_S-1) break;
        }
        int ok_B = len_S-1;
        now = len_B-1;
        while(ok_B >= 0){
            now = next_B[now][char_to_idx(S[ok_B])]-1;
            if(now < -1) break;
            --ok_B;
            if(now == -1 || ok_B == 0) break;
        }
        if(ok_A <= ok_B) cout << "-1\n";
        else{
            int answer = len_S;
            rep2(i, ok_B+1, ok_A+1) chmin(answer, abs((i<<1) - len_S));
            cout << answer << '\n';
        }
    }
    return 0;
}

ok_A = 2, ok_B = 1, len_S = 14
10

ok_A = 6, ok_B = 0, len_S = 16
4

ok_A = 6, ok_B = 3, len_S = 16
4

ok_A = 9, ok_B = 9, len_S = 10
-1

ok_A = 1, ok_B = 0, len_S = 4
2

ok_A = 0, ok_B = 3, len_S = 16
-1

ok_A = 2, ok_B = 17, len_S = 23
-1

ok_A = 16, ok_B = 19, len_S = 50
-1

ok_A = 9, ok_B = 8, len_S = 15
3

ok_A = 4, ok_B = 0, len_S = 5
1

## F
担当：nick
最初に全てを2倍すると整数のみで考えられる←下の方針だとこれの意味がなくなっている……
https://atcoder.jp/contests/agc049/tasks/agc049_d
↑元ネタ？
↓WA
i番目の有効範囲
i番目とi+1番目は独立して動けると考えてよいのか？
問題の条件はこれと一緒？
A[i - 1] - A[i] >= A[i] - A[i + 1]
1のとき X = -inf
＊R1 - A[1] >= Xを満たして、L2 <= A[1] <= R2 であるような最大のA[1]を取る
1 3 1
5 6 5

n = int(input())
l = [2*v for v in map(int, input().split())]
r = [2*v for v in map(int, input().split())]
xmin = l[0]; xmax = r[0]
for i in range(1, n-1):
    if xmax+r[i+1] < 2*l[i] or 2*r[i] < xmin+l[i+1]: print("No"); break
    xmin = max((xmin+l[i+1])//2, l[i])
    xmax = min((xmax+r[i+1])//2, r[i])
else: print("Yes")

n = int(input())
l = [2*v for v in map(int, input().split())]
r = [2*v for v in map(int, input().split())]
xmin = [l[0], l[1]]
xmax = [r[0], r[1]]
for i in range(2, n):
    if 2*xmax[i-1]-xmin[i-2] < l[i] or r[i] < 2*xmin[i-1]-xmax[i-2]: print("No"); break
    xmin.append(max(2*xmin[i-1]-xmax[i-2], l[i]))
    xmax.append(r[i])
    xmax[i-1] = min(xmax[i-1], (xmax[i-2]+xmax[i])//2)
else: print("Yes")

## G
担当：

n = int(input())
l = list(map(int, input().split()))
r = list(map(int, input().split()))
ans = 0
for d in range(-10**5+1, 10**5):
    if abs(d)*(n-1) >= 10**5: continue
    mi = 1
    ma = 10**5
    for i, (li, ri) in enumerate(zip(l, r)):
        mi = max(mi, li-d*i)
        ma = min(ma, ri-d*i)
    ans += max(ma-mi+1, 0)
print(ans)

## H
担当：shiro

メモリ制限小さすぎ、隣接行列持っただけで終わる
SCC+トポロジカルソートでDAGにできる。DAGとしてよい（強連結は1つの色で塗るのが最適）
以下のようなアルゴリズムで解ける？

1.色のついてないうち、番号が最小の頂点を選ぶ
2.それと、そこから到達できる頂点を全て同じ色で塗る
3.色++
↑嘘

DAGで2つのパスがあるとき、枝分かれした2つで同じ色を塗ることはできない
1つのパスは同じ色で塗ることができる
・DAGを最小本数のパスに分解せよという問題になる
https://kyopro.hateblo.jp/entry/2018/06/04/000659
↑これっぽい　フローでできる

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

edges = [[i - 1 for i in li()] for _ in range(m)]

S = scc(n, edges)

leader = [-1] * n
for x, v in enumerate(S):
    for i in v:
        leader[i] = x

edge2 = []
for u, v in edges:
    if leader[u] != leader[v]:
        edge2.append((leader[u], leader[v]))
N = len(S)
G = mf_graph(2 * N + 2)
sink = 2 * N
tar = 2 * N + 1
for i in range(N):
    G.add_edge(sink, i, 1)
    G.add_edge(N + i, tar, 1)
e = {}

for u, v in edge2:
    if u != v:
        G.add_edge(u, N + v, 1)

f = G.flow(sink, tar)

print(G.edges())
U = dsu(N)
ed = []
for v in G.edges():
    if v['flow'] == 1 and 0 <= v['from'] < N and N <= v['to'] < 2 * N:
        ed.append((v['from'], v['to']))

assert N - f == max(ans)
print(*ans)

## K
担当：

## L
担当：

0 1 | 2 3 みたいなグループに分けたとき、全部の数が、元いるグループと別のところにいる必要がある
少なくともi個の数が同じグループにとどまっている場合の数→包除原理？
違反がiグループであるような入れ方の数

0 1 | 2 3のとき、
それぞれのグループのmin 0 2 を取る。
これは元と違うグループにいないといけないので、かく乱順列で1通り。

1グループ違反: グループを1つ選んで、その中からそのグループにとどめるやつを選んで、残りは好きに並べる Choose(n, 1) * m * (MN - 1)!
2グループ違反: グループを2つ選んで ~~ Choose(M, 2) * N^2 * (MN - 2)!
0 1 2 3 4 5
3 2 のとき、同じグループの順序を考慮しないと10通りになる
0 2 4
(2, 4, 1, 5, 0, 3)
(2, 3, 4, 5, 0, 1), (2, 4, 0, 5, 1, 3), (3, 5, 1, 4, 0, 2), (3, 5, 0, 4, 1, 2), (3, 4, 0, 5, 1, 2), (3, 4, 1, 5, 0, 2), (2, 5, 1, 4, 0, 3), (4, 5, 0, 1, 2, 3), (2, 5, 0, 4, 1, 3)

N個のグループそれぞれがN-1個のグループに自分たちの持つM個を配布する
配布されたあと各グループがM個もっていればよい
0 1 2
3 0 5
6 7 0

2 2
0 2
2 0

i番目のグループからj番目のグループに配布する数をa[i][j]とするとsum(a[i][\*])=sum(a[\*][j])=M
a[i][i]=0

## M
担当：
## N
担当：

## O
担当：