// By DeNeRATe 杨佳宇轩
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <windows.h>

#define ll long long
#define de(x) cerr << #x << " = " << x << " "
#define rep(i, a, b) for(int i = a; i <= b; i++)
#define per(i, a, b) for(int i = a; i >= b; i--)
using namespace std;
const int maxn = 12, maxm = 1e5 + 10;

struct node { // 用结构体封装
    int squ[maxn][maxn]; // 关系矩阵
    int cnt[maxn]; // 图中每个点的度数
    int row, line; // 矩阵的行列

    inline void clean() { rep(i, 1, row) rep(j, 1, line) { squ[i][j] = 0; } } // 初始化矩阵为零矩阵

    friend istream & operator >> (istream &is, node &temp) { // 结构体重载流输入
        int u, v;
        printf("Please input the number of points in the graph\n");
        cin >> temp.row; temp.line = temp.row; // 先输入当前图的点数，之后形成一个deg = 点数的矩阵
        printf("Then please input the edge relationship of the graph with \"0 0\" as the end of the order\n");
        while(true) { // 输入每一条边，顺便记录每点度数，且形成邻接矩阵
            cin >> u >> v;
            if(!u || !v) break;
            temp.squ[u][v] = temp.squ[v][u] = 1;
            temp.cnt[u]++; temp.cnt[v]++;
        }
        printf("\n");
    }

    friend ostream & operator << (ostream &os, const node &temp) { // 结构体重载流输出，将矩阵按格式输出
        rep(i, 1, temp.row) { rep(j, 1, temp.line)
            cout << temp.squ[i][j] << " ";
            printf("\n");
        }
        printf("\n");
    }

    friend node operator * (node a, node b) { // 结构体中重载乘法为矩阵乘法
        node temp;
        temp.row = a.row, temp.line = b.line;
        temp.clean();
        rep(i, 1, temp.row) rep(j, 1, temp.line) {
            rep(k, 1, a.line) 
                temp.squ[i][j] += a.squ[i][k] * b.squ[k][j];
        }
        return temp;
    }

    inline node trans() { // 矩阵的转置操作
        node temp;
        temp.clean(); temp.row = line; temp.line = row;
        rep(i, 1, temp.row) rep(j, 1, temp.line) {
            temp.squ[i][j] = squ[j][i];
        }
        return temp;
    }
}sta, ed, tr, now; 
/*
sta为匹配图
ed为原图，被匹配图
tr为极大映射关系矩阵
now为临时映射矩阵
*/

vector<node> res; // 存放满足条件的映射矩阵
bool jud[maxn]; // 判断临时映射矩阵now中当前列是否已经有了1

inline void init() {
    printf("The first matrix is the subgraph and the second is the matched graph\n\n");
    Sleep(5000); // 等待5000ms（5s）
    cin >> sta >> ed; // 输入这两个图，转化为邻接矩阵
    tr.row = sta.row; tr.line = ed.line;
    now.row = sta.row; now.line = ed.line; // 映射矩阵规格赋值
    rep(i, 1, sta.row) rep(j, 1, ed.line) 
        if(sta.cnt[i] <= ed.cnt[j]) 
        tr.squ[i][j] = 1; // 如果sta中某点度数小于ed中某点度数则tr极大映射矩阵当前位置为true
}

inline bool check() {
    node temp = now * (now * ed).trans(); // 生成仅由sta中的点组成的ed子图
    rep(i, 1, sta.row) rep(j, 1, sta.line) 
        if(sta.squ[i][j] && !temp.squ[i][j]) return false; // 进行判断，满足sta中每一条边temp都有
    return true;
}

inline void generate(int dep) { // 每行选取一个1，且每列至多选取一个1
    if(dep > tr.row) {
        if(check()) res.push_back(now); // 如果这个映射矩阵生成了，那么就用check()函数来进行判断
        return;
    }
    rep(j, 1, tr.line) {
        if(!tr.squ[dep][j] || jud[j]) continue;
        now.squ[dep][j] = 1;
        jud[j] = true;
        generate(dep + 1);
        now.squ[dep][j] = 0;
        jud[j] = false; // 复原，以便枚举到下一个映射矩阵
    }
} // 整体递归处理

int main() {
    init(); // 初始化函数
    generate(1); // 生成所有情况的映射关系，进行判断
    if(!res.size()) { // 如果没有满足条件的子图同构的映射
        cout << "no mapping relationships\n"; 
        system("pause");
        return 0; 
    }
    printf("The mapping relationships are as follows\n");
    rep(i, 0, res.size() - 1) { // 输出每个满足条件的映射关系矩阵
        printf("%dth:\n", i);
        cout << res[i];
    }
    system("pause");
    return 0;
}

// for an idea：连上esp32 将这个图用OLED输出出来，感觉不错，哈哈哈
//时间复杂度：O(deg! * deg ^ 3) 大概1s可处理8个点连成的完全图

/*
示例：
3
1 2
1 3
0 0
4
1 2
1 3
2 3
2 4
3 4
0 0
*/

//improvement group
#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cstdio>
#include <ctime>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <unordered_map>

#define ll long long
#define ld long double
#define cl(x, y) memset((x), (y), sizeof(x))
#define rep(i, a, b) for(int i = a; i <= b; i++)
#define per(i, a, b) for(int i = a; i >= b; i--)
#define de(x) cerr << #x << " = " << x << " "
#define inc_mod(x, y) x = ((x - y) % mod + mod) % mod
#define add_mod(x, y) x = (x + y) % mod
#define mul_mod(x, y) x = (x  *  y) % mod
#define lowbit(x) (x & (-x))
#define inf 0x3f3f3f3f
#define mod_one 998244353
#define mod_two 1000000007
#define rson (x << 1 | 1)
#define lson (x << 1)
using namespace std;

char buffer[100001], *s, *t; 
inline char get_char() {
    if(s == t) {  
        t = (s = buffer) + fread(buffer, 1, 100001, stdin);
        if(s == t) return EOF;  
    }
    return *s++; 
}
inline int fread() {
    char ch; 
    int temp = 0;  
    for(ch = get_char(); ch < '0' || ch > '9'; ch = get_char());  
    while(ch >= '0' && ch <= '9') {
        temp = (temp << 1) + (temp << 3) + (ch - '0');
        ch = get_char();  
    }
    return temp;  
}
inline void file() {
    freopen(".in", "r", stdin);
    freopen(".out", "w", stdout);
}
inline int read_int() {
    int temp = 0, fac = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') { if(ch == '-') { fac = -1; } ch = getchar(); }
    while(ch >= '0' && ch <= '9') { temp = (temp << 1) + (temp << 3) + (ch ^ 48); ch  =  getchar(); }
    return temp * fac;
}
inline ll read_ll() {
    ll temp = 0, fac = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') { if(ch == '-') { fac = -1; } ch = getchar(); }
    while(ch >= '0' && ch <= '9') { temp = (temp << 1) + (temp << 3) + (ch ^ 48); ch  =  getchar(); }
    return temp * fac;
}
inline void write(int now) {
    if(now < 0) { putchar('-'), now = -now; }
    if(now > 9) { write(now / 10); }
    putchar(now % 10 + '0');
}
inline ll mul(ll l, ll r) {
    l = (l % mod_one + mod_one) % mod_one; 
    r = (r % mod_one + mod_one) % mod_one;
	ll res = l * r - (ll)((ld)l / mod_one * r + 1e-8) * mod_one;
	return res < 0 ? res + mod_one : res; 
}

namespace dijkstra {
    const ll maxn = 1e4 + 10,  maxm = 5e5 + 10;

    ll total, side, u, v, w, opt, sta;
    ll nxt[maxm << 1], head[maxn], ed[maxm << 1], cur, val[maxm << 1];
    bool jud[maxn];
    ll dist[maxn];
    priority_queue<pair<ll, ll>, vector<pair<ll, ll> >, greater<pair<ll, ll> > > mine;

    inline void solve() {
        cl(dist, 0x3f);
        dist[sta] = 0;
        mine.push(make_pair(dist[sta], sta));
        while(!mine.empty()) {
            pair<ll, ll>now = mine.top();
            mine.pop();
            if(jud[now.second]) continue;
            jud[now.second] = true;
            for(ll i = head[now.second]; i; i = nxt[i]) 
                if(dist[ed[i]]>now.first + val[i]) {
                    dist[ed[i]] = now.first + val[i];
                    mine.push(make_pair(dist[ed[i]], ed[i]));
                }
        }
    }

    inline void add_edge(ll from, ll to, ll temp) { 
        nxt[++cur] = head[from]; 
        head[from] = cur; 
        ed[cur] = to; 
        val[cur] = temp; 
    }

    inline void Main() {
        scanf("%lld %lld %lld", &total, &side, &sta);
        rep(i, 1, side) { scanf("%lld %lld %lld", &u, &v, &w); add_edge(u, v, w); }
        solve();
        rep(i, 1, total) { printf("%lld ", dist[i] == inf ? 0x7fffffff : dist[i]); }
    }
}
namespace spfa {
    const int maxn = 1e4 + 10, maxm = 5e5 + 10;

    ll total, side, u, v, w, opt, sta;
    ll nxt[maxm << 1], head[maxn], ed[maxm << 1], cur, val[maxm << 1];
    bool jud[maxn];
    ll dist[maxn];
    deque<ll> mine;

    inline void solve() {
        cl(dist, 0x3f);
        dist[sta] = 0; 
        jud[sta] = true;
        mine.push_front(sta);
        while(!mine.empty()) {
            ll now = mine.front();
            mine.pop_front();
            jud[now] = false;
            for(ll i = head[now]; i; i = nxt[i]) 
                if(dist[ed[i]] > dist[now] + val[i]) {
                    dist[ed[i]] = dist[now] + val[i];
                    if(!jud[ed[i]]) { 
                        if(mine.empty() || dist[ed[i]]>dist[mine.front()]) mine.push_back(ed[i]);
                        else mine.push_front(ed[i]);
                        jud[ed[i]] = true;
                    }
                }
        }
    }

    inline void add_edge(ll from, ll to, ll temp) { 
        nxt[++cur] = head[from]; 
        head[from] = cur; 
        ed[cur] = to; 
        val[cur] = temp; 
    }

    inline void Main() {
        scanf("%lld %lld %lld", &total, &side, &sta);
        rep(i, 1, side) { scanf("%lld %lld %lld", &u, &v, &w); add_edge(u, v, w); }
        solve();
        rep(i, 1, total) { printf("%lld ", dist[i] == inf ? 0x7fffffff : dist[i]); }
    }
}
namespace screen_Prime {
    const int maxn = 1e8 + 10;

    int prime[maxn], cnt;
    bool jud[maxn];
    int limit, test, u;

    inline void solve() {
        jud[0] = jud[1] = true;
        rep(i, 2, limit) {
            if(!jud[i]) { prime[ ++ cnt] = i; }
            for(int j = 1; j <= cnt && prime[j] * i <= limit; j++) {
                jud[i * prime[j]] = true;
                if(!(i % prime[j])) break;
            }
        }
    }

    inline void Main() {
        scanf("%d %d", &limit, &test);
        solve();
        while(test--) { scanf("%d", &u); printf("%d\n", prime[u]); }
    }
}
namespace kruskal {
    const int maxn = 5e3 + 10, maxm = 2e5 + 10;

    int total, side, u, v, w, opt;
    int fa[maxn], sum, gro;
    struct node {
        int from, to, val;
        friend bool operator < (node a, node b)
        { return a.val < b.val; }
    }line[maxm];

    inline int find_fa(int now) { return fa[now] == now ? now : fa[now] = find_fa(fa[now]); }
    inline void Main() {
        scanf("%d %d", &total, &side); 
        gro = total;
        rep(i, 1, side) { scanf("%d %d %d", &line[i].from, &line[i].to, &line[i].val); }
        rep(i, 1, total) fa[i] = i;
        sort(line + 1, line + side + 1);
        rep(i, 1, side) {
            int x = find_fa(line[i].from), y = find_fa(line[i].to);
            if(x != y) { fa[x] = y; gro--; sum += line[i].val; }
        }
        if(gro == 1) { printf("%d\n", sum); }
        else { printf("orz\n"); }
    }
}
namespace prim {
    const int maxn = 5e3 + 10, maxm = 2e5 + 10;

    int total, side, u, v, w, opt;
    int nxt[maxm << 1], head[maxn], ed[maxm << 1], cur, val[maxm << 1];
    int dist[maxn], cnt, sum;
    bool jud[maxn];
    priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > >mine;

    inline void solve() {
        cl(dist, 0x3f);
        dist[1] = 0;
        mine.push(make_pair(dist[1], 1));
        while(!mine.empty()) {
            pair<int, int>now = mine.top();
            mine.pop();
            if(jud[now.second]) continue;
            jud[now.second] = true;
            sum += now.first;
            for(int i = head[now.second]; i; i = nxt[i]) 
                if(dist[ed[i]] > val[i]) {
                    dist[ed[i]] = val[i];
                    mine.push(make_pair(dist[ed[i]], ed[i]));
                }
        }
    }

    inline void add_edge(int from, int to, int temp) { 
        nxt[++cur] = head[from]; 
        head[from] = cur; 
        ed[cur] = to; 
        val[cur] = temp; 
    }

    inline void Main() {
        scanf("%d %d", &total, &side);
        rep(i, 1, side) { scanf("%d %d %d", &u, &v, &w); add_edge(u, v, w); add_edge(v, u, w); }
        solve();
        printf("%d\n", sum);
    }   
}
namespace trisection {
    const int maxn = 15;
    const double eps = 1e-5;

    int total;
    double loc[maxn], from, to, ans;

    inline double check(double temp) {
        double now = 1.0, res = 0.0;
        rep(i, 0, total - 1) {
            res += now * loc[i];
            now *= temp;
        }
        return res;
    }

    inline void Main() {
        scanf("%d %lf %lf", &total, &from, &to);
        per(i, total, 0) { scanf("%lf", &loc[i]); }
        rep(i, 0, total - 1) { loc[i] = loc[i + 1] * (i + 1); }
        double l = from, r = to;
        while(r - l >= eps) {
            double mid = (l + r) / 2.0;
            if(check(mid)>0) l = mid, ans = mid;
            else r = mid;
        }
        printf("%.5f\n", ans);
    }
}
namespace tree_array {
    const int maxn = 1e6 + 10;

    int fro[maxn];

    inline void update(int now, int val) {
        for(; now <= maxn - 5; now += lowbit(now)) 
            fro[now] += val;
    }

    inline int get(int now) {
        int res = 0;
        for(; now; now -= lowbit(now)) 
            res += fro[now];
        return res;
    }
}
namespace line_segment_tree {
    const int maxn = 1e5 + 10;

    ll tree[maxn << 2], tag[maxn << 2], num[maxn];

    inline void push_up(ll x) { tree[x] = tree[lson] + tree[rson]; }
    inline void build(ll l, ll r, ll x) {
        ll mid = (l + r) >> 1;
        if(l == r) { tree[x] = num[l]; return; }
        build(l, mid, lson);
        build(mid + 1, r, rson);
        push_up(x);
    }

    inline void push_down(ll l, ll r, ll x) {
        ll mid = (l + r) >> 1;
        tag[lson] += tag[x]; tag[rson] += tag[x];
        tree[lson] += tag[x] * (mid - l + 1); tree[rson] += tag[x] * (r - mid);
        tag[x] = 0;
    }

    inline void update(ll from, ll to, ll l, ll r, ll x, ll temp) {
        if(from <= l && to >= r) { tag[x] += temp; tree[x] += temp * (r - l + 1); return; }
        ll mid = (l + r) >> 1;
        push_down(l, r, x);
        if(from <= mid) update(from, to, l, mid, lson, temp);
        if(to > mid) update(from, to, mid + 1, r, rson, temp);
        push_up(x);
    }

    inline ll get(ll from, ll to, ll l, ll r, ll x) {
        ll mid = (l + r) >> 1, res = 0;
        if(l >= from && r <= to) { res += tree[x]; return res; }
        push_down(l, r, x);
        if(from <= mid) res += get(from, to, l, mid, lson);
        if(to > mid) res += get(from, to, mid + 1, r, rson);
        return res;
    }
}
namespace kmp {
    const int maxn = 1e6 + 10;

    char a[maxn], b[maxn];
    int lena, lenb;
    int lost[maxn];

    inline void get_lost() {
        int loc = 0;
        rep(i, 1, lenb - 1) {
            while(loc && b[i] != b[loc]) loc = lost[loc];
            if(b[i] == b[loc]) loc++;
            lost[i + 1] = loc;
        }
    }

    inline void solve() {
        int loc = 0;
        rep(i, 0, lena - 1) {
            while(loc && a[i] != b[loc]) loc = lost[loc];
            if(a[i] == b[loc]) loc++;
            if(loc == lenb) { printf("%d\n", i - lenb + 2); }
        }
        rep(i, 1, lenb) { printf("%d ", lost[i]); }
    }

    inline void Main() {
        scanf("%s", a); lena = strlen(a);
        scanf("%s", b); lenb = strlen(b);
        get_lost();
        solve();
    }
}
namespace multiplication_lca {  
    const int maxn = 5e5 + 10;

    int total, test, root, u, v, w, opt;
    int nxt[maxn << 1], head[maxn], ed[maxn << 1], cur, val[maxn << 1];
    int dep[maxn], anc[maxn][21], len[maxn][20];

    inline void dfs(int now, int pre) {
        dep[now] = dep[pre] + 1;
        rep(i, 1, 20) { 
            anc[now][i] = anc[anc[now][i - 1]][i - 1];  
            len[now][i] = len[now][i - 1] + len[anc[now][i - 1]][i - 1];
        }
        for(int i = head[now]; i; i = nxt[i]) {
            if(ed[i] == pre) continue;
            anc[ed[i]][0] = now;
            len[ed[i]][0] = val[i];
            dfs(ed[i], now);
        }
    }

    inline int solve(int x, int y) {
        if(dep[x] < dep[y]) swap(x, y);
        per(i, 20, 0) { if(dep[anc[x][i]] >= dep[y]) x = anc[x][i]; }
        if(x == y) return x;
        per(i, 20, 0) if(anc[x][i] != anc[y][i]) x = anc[x][i], y = anc[y][i];
        return anc[x][0];
    }

    inline void add_edge(int from, int to, int temp) { 
        nxt[++cur] = head[from]; 
        head[from] = cur; 
        ed[cur] = to; 
        val[cur] = temp; 
    }

    inline void Main() {
        scanf("%d %d %d", &total, &test, &root);
        rep(i, 2, total) { scanf("%d %d", &u, &v); add_edge(u, v, 1); add_edge(v, u, 1); }
        dfs(root, 0);
        while(test--) {
            scanf("%d %d", &u, &v);
            printf("%d\n", solve(u, v));
        }
    }
}
namespace negative_loop {
    const int maxn = 2e3 + 10, maxm = 3e3 + 10;

    ll total, side, u, v, w, opt, test;
    ll nxt[maxm << 1], head[maxn], ed[maxm << 1], cur, val[maxm << 1];
    bool jud[maxn], flag = true;
    ll dist[maxn], cnt[maxn];
    queue<ll> mine;

    inline void solve() {
        cl(dist, 0x3f);
        dist[1] = 0; 
        jud[1] = true;
        mine.push(1); cnt[1]++;
        while(!mine.empty()) {
            ll now = mine.front();
            mine.pop();
            jud[now] = false;
            for(ll i = head[now]; i; i = nxt[i]) 
                if(dist[ed[i]] > dist[now] + val[i]) {
                    dist[ed[i]] = dist[now] + val[i];
                    if(!jud[ed[i]]) { 
                        mine.push(ed[i]);
                        if(++cnt[ed[i]] >= total + 1) { flag = false; return; }
                        jud[ed[i]] = true;
                    }
                }
        }
    }

    inline void clean() { cl(jud, false); cl(cnt, 0); flag = true; cl(head, 0); cur = 0; while(!mine.empty()) mine.pop(); }
    inline void add_edge(ll from, ll to, ll temp) { 
        nxt[++cur] = head[from]; 
        head[from] = cur; 
        ed[cur] = to; 
        val[cur] = temp; 
    }

    inline void Main() {
        cin >> test;
        while(test--) {
            clean();
            scanf("%lld %lld", &total, &side);
            rep(i, 1, side) { scanf("%lld %lld %lld", &u, &v, &w); add_edge(u, v, w); if(w >= 0) add_edge(v, u, w); }
            solve();
            if(flag) { printf("NO\n"); }
            else {  printf("YES\n"); }
        }
    }
}
namespace matrix {
    const int maxn = 4;

    ll test, u;
    struct node { ll squ[maxn][maxn]; }now, base, cop;

    inline void matrix_fast(node &a, node b) {
        rep(i, 1, 3) rep(j, 1, 3) cop.squ[i][j] = 0;
        rep(i, 1, 3) rep(j, 1, 3) rep(k, 1, 3)
        (cop.squ[i][j] += (a.squ[i][k] * b.squ[k][j]) % mod_two) %= mod_two;
        rep(i, 1, 3) rep(j, 1, 3) a.squ[i][j] = cop.squ[i][j];
    }

    inline void solve(ll limit) {
        while(limit) {
            if(limit & 1) { matrix_fast(now, base); }
            matrix_fast(base, base); limit >>= 1;
        }
    }

    inline void clean() {
        base.squ[1][1] = base.squ[1][2] = base.squ[2][3] = base.squ[3][1] = 1;
        now.squ[1][1] = now.squ[1][2] = now.squ[1][3] = 1;
        base.squ[1][3] = base.squ[2][1] = base.squ[2][2] = base.squ[3][2] = base.squ[3][3] = 0;
        now.squ[2][1] = now.squ[2][2] = now.squ[2][3] = 0;
        now.squ[3][1] = now.squ[3][2] = now.squ[3][3] = 0;
    }
    inline void Main() {
        scanf("%lld", &test);
        while(test--) {
            clean();
            scanf("%lld", &u);
            if(u <= 3) { cout << "1" << endl; continue; }
            solve(u - 3);
            printf("%lld\n", now.squ[1][1]);
        }
    }
}
namespace st_list {
    const int maxn = 1e5 + 10;

    int num[maxn];
    int anc[maxn][21];
    int total, test, u, v;

    inline int solve(int l, int r) {
        int temp = (log2(double(r - l + 1)));
        return max(anc[l][temp], anc[r - (1 << temp) + 1][temp]);
    }

    inline void Main() {
        scanf("%d %d", &total, &test);
        rep(i, 1, total) { scanf("%d", &num[i]); anc[i][0] = num[i]; }
        for(int j = 1; (1 << j) <= total; j++) 
            for(int i = 1; i + (1 << j) - 1 <= total; i++)
                anc[i][j] = max(anc[i][j - 1], anc[i + (1 << (j - 1))][j - 1]); 
        while(test--) {
            scanf("%d %d", &u, &v);
            printf("%d\n", solve(u, v));
        }
    }
}
namespace antichrist {
    const int maxn = 1e5 + 10;

    int inv[maxn], fac[maxn], inv_fac[maxn];

    inline int fast(int a, int b) { 
        int res = 1; 
        while(b) { 
            if(b & 1) res = res * a % mod_one; 
            a = a * a % mod_one; b >>= 1; 
        } 
        return res % mod_one; 
    }

    inline void Main() {
        inv[0] = inv[1] = 1; fac[0] = fac[1] = 1;
        rep(i, 2, maxn - 5) {
            inv[i] = (mod_one - mod_one / i) * inv[mod_one % i] % mod_one;
            fac[i] = fac[i - 1] * i % mod_one;
        }
        inv_fac[maxn - 5] = fast(fac[maxn - 5], mod_one - 2);
        per(i, maxn - 6, 0) { inv_fac[i] = inv_fac[i + 1] * (i + 1) % mod_one; }
    }
}
namespace cantor {
    const int maxn = 1e6 + 10;

    ll num[maxn], fro[maxn];
    ll total, fac[maxn], ans;

    inline void update(ll now, ll val) { while(now <= maxn - 5) { (fro[now] += val) %= mod_one; now += lowbit(now); } }
    inline ll get(ll now) { ll res = 0; while(now) { (res += fro[now]) %= mod_one; now -= lowbit(now); } return res; }
    inline void solve() {
        rep(i, 1, total) {
            ll temp = num[i] - 1 - get(num[i]);
            (ans += temp * fac[total - i] % mod_one) %= mod_one;
            update(num[i], 1);
        }
    }

    inline void Main() {
        scanf("%lld", &total); 
        fac[0] = 1;
        rep(i, 1, total) { scanf("%lld", &num[i]); fac[i] = fac[i - 1] * i % mod_one; }
        solve();
        printf("%lld\n", ans + 1);
    }
}
namespace differential {
    const int maxn = 5e3 + 10;

    int total, test;
    int u, v, w, opt;
    int nxt[maxn << 1], head[maxn], ed[maxn << 1], cur, val[maxn << 1];
    int cnt[maxn], dist[maxn];
    bool vis[maxn], jud = true;
    deque<int> temp;

    inline void spfa() {
        cl(dist, 0x3f); 
        dist[0] = 0;
        temp.push_front(0);
        vis[0] = true;
        cnt[0] = 1;
        while(!temp.empty()) {
            int now = temp.front();
            temp.pop_front();
            vis[now] = false;
            for(int i = head[now]; i; i = nxt[i])
                if(dist[ed[i]] > dist[now] + val[i]) {
                    dist[ed[i]] = dist[now] + val[i];
                    if(!vis[ed[i]]) {
                        if(temp.empty() || dist[ed[i]] < dist[temp.front()]) temp.push_front(ed[i]);
                        else temp.push_back(ed[i]);
                        vis[ed[i]] = true;
                        if((++cnt[ed[i]]) > total) { printf("No\n"); exit(0); }
                    }
                }
        }
    } 

    inline void add_edge(int from, int to, int tot) { 
        nxt[++cur] = head[from]; 
        head[from] = cur; 
        ed[cur] = to; 
        val[cur] = tot; 
    }

    inline void Main() {
        scanf("%d %d", &total, &test);
        while(test--) {
            scanf("%d", &opt);
            if(opt == 1) { scanf("%d %d %d", &u, &v, &w); add_edge(u, v, -w); }
            else if(opt == 2) { scanf("%d %d %d", &u, &v, &w); add_edge(v, u, w); }
            else { scanf("%d %d", &u, &v); add_edge(u, v, 0); }
        } 
        rep(i, 1, total) add_edge(0, i, 0);
        spfa();
        printf("Yes\n");
    }
}
namespace tarjan_scc {
    const int maxn = 1e4 + 10, maxm = 1e5 + 10;

    int total, side, u, v, w, opt;
    int num[maxn], dfn[maxn], low[maxn], dfn_num, col_num, col[maxn], size[maxn];
    int nxt[maxm << 1], head[maxn], ed[maxm << 1], cur;
    int stack[maxn], top;
    bool jud[maxn];

    inline void dfs(int now, int pre) {
        low[now] = dfn[now] = ++dfn_num;
        stack[++top] = now;
        jud[now] = true;
        for(int i = head[now]; i; i = nxt[i]) {
            if(ed[i] == pre) continue;
            if(!dfn[ed[i]]) {
                dfs(ed[i], now);
                low[now] = min(low[now], low[ed[i]]);
            } else if(jud[ed[i]]) 
                low[now] = min(low[now], dfn[ed[i]]);
        }
        if(dfn[now] == low[now]) {
            col_num++;
            while(stack[top] != now) {
                int temp = stack[top--];
                jud[temp] = false;
                col[temp] = col_num;
                size[col_num]++;
            }
            top--;
            jud[now] = false;
            col[now] = col_num;
            size[col_num]++;
        }
    }   
}
namespace cut_point {
    const int maxn = 2e4 + 10, maxm = 1e5 + 10;

    int total, side, u, v, w, opt, ans;
    int nxt[maxm << 1], head[maxn], ed[maxm << 1], cur;
    bool jud[maxn];
    int dfn[maxn], low[maxn], dfn_num;

    inline void dfs(int now, int pre) {
        dfn[now] = low[now] = ++dfn_num;
        int child = 0;
        for(int i = head[now]; i; i = nxt[i]) {
            if(ed[i] == pre) continue;
            if(!dfn[ed[i]]) {
                child++;
                dfs(ed[i], now);
                low[now] = min(low[now], low[ed[i]]);
                if(pre != 0 && low[ed[i]] >= dfn[now] && !jud[now]) 
                    jud[now] = true,  ans++;
            } else { low[now] = min(low[now], dfn[ed[i]]); }
        }
        if(pre == 0 && child >= 2 && !jud[now]) { jud[now] = true; ans++; }
    }
}
namespace bridge {
    const int maxn = 2e4 + 10, maxm = 1e5 + 10;

    int nxt[maxm << 1], head[maxn], ed[maxm << 1], cur;
    int dfn[maxn], low[maxn], dfn_num;
    bool jud[maxm << 1];
    int total, side, u, v, w, opt, ans;

    inline void dfs(int now, int pre) {
        dfn[now] = low[now] = ++dfn_num;
        for(int i = head[now]; i; i = nxt[i]) {
            if(ed[i] == pre) continue;
            if(!dfn[ed[i]]) {
                dfs(ed[i], now);
                low[now] = min(low[now], low[ed[i]]);
                if(low[ed[i]] > dfn[now]) { jud[i] = jud[i ^ 1] = true; ans++; }
            } else low[now] = min(low[now], dfn[ed[i]]);
        }
    }
}
namespace k_nim {
    // 这里只打了1 - NIM问题
    const int maxn = 1e4 + 10;

    int num[maxn], total, test;

    inline bool solve() {
        int res = 0;
        rep(i, 1, total) { res ^= num[i]; }
        return res;
    }

    inline void Main() {
        scanf("%d", &test);
        while(test--) {
            scanf("%d", &total);
            rep(i, 1, total) scanf("%d", &num[i]);
            if(solve()) { printf("Yes\n"); }
            else { printf("No\n"); }
        }
    }
}
namespace gcd {
    inline int gcd(int x, int y) {
        return (!y) ? x : gcd(y, x % y);
    }
}
namespace ex_gcd {
    ll test, a, b, c, x, y, r, d, cnt;

    inline ll init(ll x, ll y) {
        if(!y) { x = 1; y = 0; return x; }
        ll p = init(y, x % y);
        ll temp = y; y = x - (x / y) * y; x = temp;
        return p;
    }

    inline void solve() {
        x = y = r = d = cnt = 0;
        r = init(a, b);
        if(c % r) { printf("-1\n"); return; }
        ll x0 = x * (c / r), y0 = y * (c / r);
        ll p = b / r, q = a / r;
        if(x0 < 0) { ll k = (ceil)((1.0 - x0) / p); x0 += p * k; y0 -= q * k; }
        else { ll k = (x0 - 1) / p; x0 -= p * k; y0 += q * k; }
        if(y0 > 0) {
            printf("%lld ", (y0 - 1) / q + 1);
            printf("%lld %lld %lld %lld\n", x0, (y0 - 1) % q + 1, x0 + p * ((y0 - 1) / q), y0);
        } else {
            printf("%lld ", x0);
            int o = ceil((1.0 - y0) / q);
            printf("%lld\n", y0 + q * o);
        }
    }

    inline void Main() {
        scanf("%lld", &test);
        while(test--) {
            scanf("%lld %lld %lld", &a, &b, &c);
            solve();
        }
    }
}
namespace fhq_treap {
    const int maxn = 1e5 + 10;

    int test, u, v, w, opt, root;
    int weight[maxn], val[maxn], size[maxn], child[maxn][2], cnt;

    inline void update(int now) { size[now] = size[child[now][1]] + size[child[now][0]] + 1; }
    inline int new_node(int temp) { weight[++cnt] = rand(); val[cnt] = temp; size[cnt] = 1; return cnt; }
    inline void split(int now, int limit, int &a, int &b) {
        if(!now) { a = b = 0; return; }
        if(val[now] <= limit) { a = now; split(child[now][1], limit, child[now][1], b); }
        else { b = now; split(child[now][0], limit, a, child[now][0]); }
        update(now);
    }

    inline int merge(int a, int b) {
        if(!a || !b) { return a + b; }
        if(weight[a] < weight[b]) { child[a][1] = merge(child[a][1], b); update(a); return a; }
        else { child[b][0] = merge(a, child[b][0]); update(b); return b; }
    }

    inline int rank(int now, int limit) {
        while(true) {
            if(size[child[now][0]] >= limit) now = child[now][0];
            else if(size[child[now][0]] + 1 == limit) return val[now];
            else limit -= size[child[now][0]] + 1, now = child[now][1];
        }
    }

    inline void Main() {
        scanf("%d", &test);
        while(test--) {
            scanf("%d %d", &opt, &u);
            int x = 0, y = 0, z = 0;
            if(opt == 1) { split(root, u - 1, x, y); root = merge(merge(x, new_node(u)), y); }
            else if(opt == 2) { split(root, u - 1, x, y); split(y, u, y, z); root = merge(merge(x, merge(child[y][0], child[y][1])), z); }
            else if(opt == 3) { split(root, u - 1, x, y); printf("%d\n", size[x] + 1); root = merge(x, y); }
            else if(opt == 4) { printf("%d\n", rank(root, u)); }
            else if(opt == 5) { split(root, u - 1, x, y); printf("%d\n", rank(x, size[x])); root = merge(x, y); }
            else { split(root, u, x, y); printf("%d\n", rank(y, 1)); root = merge(x, y); }
        }
    }
}
namespace descartes {
    const int maxn = 1e7 + 10;

    int child[maxn][2], num[maxn];
    int stack[maxn], top;
    int total, u, v, w, opt;
    ll ans_one, ans_two;

    inline void Main() {
        scanf("%d", &total);
        rep(i, 1, total) { 
            num[i] = read_int();
            int k = top;
            while(k && num[stack[k]] >= num[i]) { k--; }
            if(k) { child[stack[k]][1] = i; }
            if(k != top) { child[i][0] = stack[k + 1]; }
            top = k;
            stack[++top] = i;
        }
        rep(i, 1, total) { ans_one ^= 1ll * i * (child[i][0] + 1); ans_two ^= 1ll * i * (child[i][1] + 1); }
        printf("%lld %lld\n", ans_one, ans_two);
    }
}
namespace minimalist_representation {
    const int maxn = 3e5 + 10;

    int num[maxn];
    int len, pos_one, pos_two, k, ans;

    inline void solve() {
        pos_one = 0, pos_two = 1, k = 0;
        while(pos_one < len && pos_two < len && k < len) {
            if(num[(pos_one + k) % len] == num[(pos_two + k) % len]) k++;
            else { 
                (num[(pos_one + k) % len] < num[(pos_two + k) % len]) ? pos_two = (pos_two + k + 1) : pos_one = (pos_one + k + 1); 
                if(pos_one == pos_two) pos_one++;
                k = 0;   
            }
        }
        ans = min(pos_one, pos_two);
        rep(i, 0, len - 1) { printf("%d ", num[(ans + i) % len]); }
    }

    inline void Main() {
        scanf("%d", &len);
        rep(i, 0, len - 1) scanf("%d", &num[i]);
        solve();
    }
}
namespace manacher {
    const int maxn = 1.5e7 + 10;

    char num[maxn << 1];
    int len, rou[maxn << 1];
    int temp, dist, ans;

    inline void char_read() {
        char ch = getchar();
        num[0] = '~'; num[len = 1] = '|';
        while(ch<'a' || ch>'z') ch = getchar();
        while(ch >= 'a' && ch <= 'z') num[++len] = ch, num[++len] = '|', ch = getchar();
    }

    inline void solve() {
        rep(i, 1, len) {
            if(i <= dist) { rou[i] = min(dist - i + 1, rou[(temp << 1) - i]); }
            while(num[i + rou[i]] == num[i - rou[i]]) rou[i]++;
            if(dist < i + rou[i]) temp = i, dist = i + rou[i] - 1;
            ans = max(ans, rou[i]);
        }
        printf("%d\n", ans - 1);
    }

    inline void Main() {
        char_read();
        solve();
    }
}
namespace crt {
    ll ans, m = 1, total, a[12], c[12];

    inline ll ex_gcd(ll a, ll b, ll &x, ll &y) {
        if(!b) { x = 1;y = 0; return a; }
        ll res = ex_gcd(b, a % b, y, x);
        y -= (a / b) * x;
        return res;
    }

    inline ll china(ll *w, ll *r) {
        for(int i = 1; i <= total; i++) m *= w[i];
        for(int i = 1; i <= total; i++){
            ll m1 = m / w[i], x, y;
            ll d = ex_gcd(m1, w[i], x, y);
            ans = (ans + m1 * x * r[i]) % m;
        }
        if(ans < 0) ans += m;
        return ans;
    }

    inline void Main() {
        scanf("%lld", &total);
        for(int i = 1; i <= total; i++) scanf("%lld %lld", &a[i], &c[i]);
        printf("%lld", china(a, c));
    }
}
namespace ex_crt {
    const int maxn = 1e5 + 10;

    ll a[maxn], m[maxn], x, y;
    ll total;

    inline ll ex_gcd(ll x, ll y) {
        if(!y) { x = 1; y = 0; return x; }
        ll r = ex_gcd(y, x % y);
        ll temp = y; y = x - (x / y) * y; x = temp;
        return r;
    }

    inline void solve() {
        ll a1 = a[1], m1 = m[1];
        rep(i, 2, total) {
            x = y = 0;
            ll a2 = a[i], m2 = m[i];
            ll r = ex_gcd(m1, m2);
            if((a2 - a1) % r) { printf("-1\n"); return; }
            ll t = m2 / r, p = (a2 - a1) / r;
            ll x0 = (p * x % t + t) % t;
            a1 = m1 * x0 + a1;
            m1 = m1 * m2 / r;
            if(a1 < 0) a1 += m1;
        }
        printf("%lld\n", a1 % m1);
    }

    inline void Main() {
        scanf("%lld", &total);
        rep(i, 1, total) { scanf("%lld %lld", &m[i], &a[i]); }
        solve();
    }
}
namespace ac_automaton {
    const int maxn = 2e5 + 10, maxm = 2e6 + 10;

    char num[maxn], temp[maxm];
    int len, total, ans[maxn];
    int child[maxn][30], lost[maxn], sig[maxn], size;
    int queue[maxn], head = 1, tail;

    inline void update(int id) {
        int loc = 0, s = strlen(num + 1);
        rep(i, 1, s) {
            int to = (num[i] - 'a' + 1);
            if(!child[loc][to]) child[loc][to] = ++size;
            loc = child[loc][to];
        }
        sig[id] = loc;
    }

    inline void get_lost() {
        rep(i, 1, 26) if(child[0][i]) { queue[++tail] = child[0][i]; }
        while(head <= tail) {
            int now = queue[head++];
            rep(i, 1, 26) {
                if(child[now][i]) { lost[child[now][i]] = child[lost[now]][i]; queue[++tail] = child[now][i]; }
                else { child[now][i] = child[lost[now]][i]; }
            }
        }
    }

    inline void solve() {
        int now = 0;
        rep(i, 1, len) {
            int to = (temp[i] - 'a' + 1);
            now = child[now][to];
            ans[now]++;
        }
        per(i, size, 1) ans[lost[queue[i]]] += ans[queue[i]];
    }

    inline void Main() {
        scanf("%d", &total);
        rep(i, 1, total) { scanf("%s", num + 1); update(i); }
        get_lost();
        scanf("%s", temp + 1); len = strlen(temp + 1);
        solve();
        rep(i, 1, total) { printf("%d\n", ans[sig[i]]); }
    }
}
namespace sam {
	const int maxn = 2e6 + 10;
	
	int total, u, v, w, opt;
	ll ans;
	char num[maxn];
	struct node {
		int ch[30];
		int len, cnt, lost;
	}state[maxn << 1];
	int size, last;
	int nxt[maxn << 1], head[maxn << 1], ed[maxn << 1], cur;

	inline void update(int now) {
		int cur = ++size;
		state[cur].len = state[last].len + 1;
		state[cur].cnt = 1;
		int loc = last;
		while(loc != -1 && !state[loc].ch[now]) {
			state[loc].ch[now] = cur;
			loc = state[loc].lost;
		}		
		if(loc == -1) state[cur].lost = 0;
		else {
			int to = state[loc].ch[now];
			if(state[to].len == state[loc].len + 1) state[cur].lost = to;
			else {
				int clone = ++size;
				state[clone].lost = state[to].lost;
				rep(i, 1, 26) state[clone].ch[i] = state[to].ch[i];
				state[clone].len = state[loc].len + 1;
				while(loc != -1 && state[loc].ch[now] == to) {
					state[loc].ch[now] = clone;
					loc = state[loc].lost;
				}
				state[cur].lost = state[to].lost = clone;
			}
		}
		last = cur;
	}
	
	inline void solve(int now) {
		for(int i = head[now]; i; i = nxt[i]) {
			solve(ed[i]);
			state[now].cnt += state[ed[i]].cnt;
		}
		if(state[now].cnt != 1) ans = max(ans, 1ll * state[now].len * state[now].cnt);
	}
	
	inline void add_edge(int from, int to) { 
        nxt[++cur] = head[from]; 
        head[from] = cur; 
        ed[cur] = to; 
    }

	inline void Main() {
		scanf("%s", num + 1);
		total = strlen(num + 1);
		state[0].lost = -1;
		rep(i, 1, total) { update(num[i] - 'a' + 1);	 }
		rep(i, 1, size) add_edge(state[i].lost, i);
		solve(0);
		printf("%d\n", ans);
	}
}
namespace pam {
	const int maxn = 5e5 + 10;
	
	char num[maxn];
	struct node {
		int ch[30];
		int len, cnt, link;
	}state[maxn];
	int cop[maxn], total, size = 1, k, temp, pos, last;
	
	inline int get(int now) {
		while(cop[pos] != cop[pos - state[now].len - 1]) now = state[now].link;
		return now;
	}
	
	inline void update(int now) {
		cop[++pos] = now;
		int loc = get(last);
		if(!state[loc].ch[now]) {
			int cur = ++size;
			state[cur].len = state[loc].len + 2;
			int to = get(state[loc].link);
			state[cur].link = state[to].ch[now];
			state[loc].ch[now] = cur;
			state[cur].cnt = state[state[cur].link].cnt + 1;
			temp = cur;
		} else { temp = state[loc].ch[now]; }
		last = state[loc].ch[now];
	}
	
	inline void Main() {
		scanf("%s", num + 1); total = strlen(num + 1);
		state[0].link = state[1].link = 1;
		state[1].len = -1;
		rep(i, 1, total) {
			num[i] = (char)(((int)num[i] - 97 + k) % 26 + 97);
			update(num[i] - 'a' + 1);
			printf("%d ", k = state[temp].cnt);
		}
	}
}
namespace lcs {
    const int maxn = 1e5 + 10;

    int loc[maxn] ,cop[maxn];
    int fro[maxn];
    int total, ans, u, v, w, opt;

    inline void update(int now, int temp) {
        while(now <= maxn - 5) {
            fro[now] = max(fro[now], temp);
            now += lowbit(now);
        }
    }

    inline int get(int now) {
        int res = 0;
        while(now) {
            res = max(res, fro[now]);
            now -= lowbit(now);
        }
        return res;
    }

    inline void Main() {
        total = read_int();
        rep(i, 1, total) {
            u = read_int();
            loc[u] = i;
        }
        rep(i, 1, total) {
            u = read_int();
            cop[i] = loc[u];
        }
        rep(i, 1, total) {
            int res = get(cop[i]);
            ans = max(ans, res + 1);
            update(cop[i], res + 1);
        }
        write(ans);
    }
}
namespace prufer {
    const int maxn = 5e6 + 10;

    int total, u, v, w, opt;
    int fa[maxn], sig[maxn];
    int loc = 1, d[maxn], vis[maxn];
    ll ans;

    inline void fa_prufer(){
        rep(i, 1, total - 1) {
            fa[i] = read_int();
            d[i]++;
            d[fa[i]]++;
        }
        rep(i, 1, total) 
            if(d[i] == 1) {
                loc = i;
                break;
            }
        rep(i, 1, total - 2) {
            while(d[loc] != 1) loc++;
            sig[i] = fa[loc];
            d[loc]--;
            while(i < total - 1 && (--d[sig[i]]) == 1 && sig[i] < loc) {
                sig[i + 1] = fa[sig[i]];
                i++;
            }
        }
        rep(i, 1, total - 2) ans ^= (1ll * i * sig[i]);
        printf("%lld\n", ans);
    }

    inline void prufer_fa() {
        rep(i, 1, total - 2) sig[i] = read_int(), vis[sig[i]]++;
        rep(i, 1, total) {
            if(!vis[i] && !loc) loc = i;
            d[i] = vis[i] + 1;
        }
        sig[total - 1] = total;
        rep(i, 1, total - 1) {
            while(d[loc] != 1) loc++;
            fa[loc] = sig[i];
            d[loc]--;
            while(i < total && (--d[sig[i]]) == 1 && sig[i] < loc) {
                fa[sig[i]] = sig[i + 1];
                i++;
            }
        }
        rep(i, 1, total - 1) ans ^= (1ll * i * fa[i]); 
        printf("%lld\n", ans);
    }

    inline void Main() {
        total = read_int();
        opt = read_int();
        if(opt == 1) fa_prufer();
        else prufer_fa();
    }
}
namespace convex_hull {
    const int maxn = 1e5 + 10;

    int total, u, v, w, opt;
    struct node {
        double x, y;

        friend double operator ^ (node a, node b) { return a.x * b.y - a.y * b.x; }
        friend double operator * (node a, node b) { return a.x * b.x + a.y + b.y; }
        friend node operator + (node a, node b) { return node { a.x + b.x, a.y + b.y }; }
        friend node operator - (node a, node b) { return node { a.x - b.x, a.y - b.y }; }
        friend bool operator < (node a, node b) {
            if(a.x == b.x) return a.y < b.y;
            else return a.x < b.x;
        }
    }dot[maxn];
    int stack[maxn], top;
    double ans;
    bool vis[maxn];

    inline double calc(int a, int b, int c) {
        return (dot[b] - dot[a]) ^ (dot[c] - dot[a]);
    }

    inline double distance(int a, int b) {
        return sqrt((dot[a].x - dot[b].x) * (dot[a].x - dot[b].x) + (dot[a].y - dot[b].y) * (dot[a].y - dot[b].y));
    }

    inline void solve() {
        stack[top = 1] = 1;
        vis[1] = true;
        rep(i, 2, total) {
            while(top >= 2 && calc(stack[top - 1], stack[top], i) < double(0)) vis[stack[top--]] = false;
            stack[++top] = i;
            vis[i] = true;
        }
        int temp = top;
        per(i, total - 1, 1) {
            while(top > temp && calc(stack[top - 1], stack[top], i) < double(0)) vis[stack[top--]] = false;
            stack[++top] = i;
            vis[i] = true;
        }
        rep(i, 1, top - 1) ans += distance(stack[i], stack[i + 1]);
        printf("%.2f\n", ans);
    }

    inline void Main() {
        total = read_int();
        rep(i, 1, total) scanf("%lf %lf", &dot[i].x, &dot[i].y);
        sort(dot + 1, dot + total + 1);
        solve();
    }
}
namespace subsequence_automata {
    const int maxn = 1e6 + 10;

    int num[maxn], cop[maxn];
    int total, len, u, v, w, opt, type, test, limit;
    vector<int> loc[maxn];

    inline void Main() {
        type = read_int(); 
        total = read_int(); test = read_int(); limit = read_int();
        rep(i, 1, total) num[i] = read_int();
        rep(i, 1, total) loc[num[i]].push_back(i);
        while(test--) {
            len = read_int();
            rep(i, 1, len) cop[i] = read_int();
            int last = 0;
            bool jud = true;
            rep(i, 1, len) {
                vector<int>::iterator iter = upper_bound(loc[cop[i]].begin(), loc[cop[i]].end(), last);
                if(iter == loc[cop[i]].end()) { jud = false; break; }
                else last = *iter;
            }
            if(!jud) printf("No\n");
            else printf("Yes\n");
        }
    }
}
namespace lichao_line_segment_tree {
    const int maxn = 5e4 + 10;

    int test, w;
    double u, v;
    struct node {
        double k, b;

        inline double calc(int x) 
        { return k * (x - 1) + b; }
    }line[maxn << 2];
    char opt[10];

    inline void update(int x, int l, int r, node now) {
        int mid = (l + r) >> 1;
        if(now.calc(l) >= line[x].calc(l) && now.calc(r) >= line[x].calc(r)) {
            line[x] = now;
            return;
        }
        if(l == r) return;
        if(now.calc(mid) >= line[x].calc(mid)) swap(now, line[x]);
        if(now.calc(l) >= line[x].calc(l)) update(lson, l, mid, now);
        if(now.calc(r) >= line[x].calc(r)) update(rson, mid + 1, r, now);
    }

    inline double get(int x, int l, int r, int loc) {
        int mid = (l + r) >> 1;
        double res = line[x].calc(loc);
        if(loc < mid) return max(res, get(lson, l, mid, loc));
        if(loc > mid) return max(res, get(rson, mid + 1, r, loc));
        return res;
    }

    inline void Main() {
        test = read_int();
        while(test--) {
            scanf("%s", opt + 1);
            if(opt[1] == 'P') {
                scanf("%lf %lf", &u, &v);
                update(1, 1, maxn - 5, node{ v, u });
            } else {
                w = read_int();
                int temp = int(get(1, 1, maxn - 5, w)) / 100;
                printf("%d\n", temp);
            }
        }
    }
}
namespace linear_base {
    const int maxn = 60;

    ll base[maxn], num[maxn];
    ll ans, total;

    inline void insert(ll now) {
        per(i, maxn - 2, 0) {
            if(!((now >> i) & 1)) continue;
            if(!base[i]) {
                base[i] = now;
                break;
            } else now ^= base[i];
        }
    }

    inline void Main() {
        total = read_ll();
        rep(i, 1, total) {
            num[i] = read_ll();
            insert(num[i]);
        }
        per(i, maxn - 2, 0) {
            if(ans & (1ll << i)) continue;
            else ans ^= base[i];
        }
        printf("%lld\n", ans);
    }
}
namespace line_segment_tree_partition {
    const int maxn = 1e5 + 10;

    struct node { int x, y; }line[maxn];
    vector<node> mine[maxn << 2];
    vector<int> time[maxn];
    int total, side, u, v, w, opt, test;
    int fa[maxn], dep[maxn], size[maxn];
    pair<int, int> con[maxn];
    int stack[maxn], top;

    inline int find_fa(int now) {
        if(fa[now] == now) return now;
        else return find_fa(fa[now]);
    }

    inline void merge(int x, int y) {
        if(dep[x] < dep[y]) swap(x, y);
        fa[y] = x;
        stack[++top] = y;
        size[x] += size[y];
        if(dep[x] == dep[y]) dep[x]++, con[y] = make_pair(1, size[y]);
        else con[y] = make_pair(0, size[y]);
    }

    inline void update(int x, int l, int r, int from, int to, int loc) {
        if(from <= l && to >= r) { mine[x].push_back(line[loc]); return; }
        int mid = (l + r) >> 1;
        if(from <= mid) update(lson, l, mid, from, to, loc);
        if(to > mid) update(rson, mid + 1, r, from, to, loc);
    }

    inline void solve(int x, int l, int r) {
        int last = top;
        rep(i, 0, int(mine[x].size()) - 1) {
            node now = mine[x][i];
            int a = find_fa(now.x), b = find_fa(now.y);
            if(a != b) merge(a, b);
        }
        if(l == r) { 
            if(size[find_fa(1)] != total) printf("Disconnected\n");
            else printf("Connected\n"); 
        }
        int mid = (l + r) >> 1;
        if(r > l) {
            solve(lson, l, mid);
            solve(rson, mid + 1, r);
        }
        for(; top > last; top--) {
            dep[fa[stack[top]]] -= con[stack[top]].first;
            size[fa[stack[top]]] -= con[stack[top]].second;
            fa[stack[top]] = stack[top];
            con[stack[top]] = make_pair(0, 0);
        }
    }

    inline void Main() {
        total = read_int(); side = read_int();
        rep(i, 1, side) line[i].x = read_int(), line[i].y = read_int();
        rep(i, 1, total) fa[i] = i, size[i] = 1, dep[i] = 1;
        test = read_int();
        rep(i, 1, test) {
            opt = read_int();
            rep(j, 1, opt) {
                u = read_int();
                time[u].push_back(i);
            }
        }
        rep(i, 1, side) {
            u = 0; v = 0;
            rep(j, 0, int(time[i].size()) - 1) {
                v = time[i][j];
                if(v == u + 1) { u = v; continue; }
                update(1, 1, test, u + 1, v - 1, i);
                u = v;
            }
            if(v != test) update(1, 1, test, u + 1, test, i);
        }
        solve(1, 1, test);
    }
}
namespace tree_chain_splitting {
    const int maxn = 1e5 + 10;

    int total, test, root, mod, u, v, w, opt;
    int num[maxn];
    int dfn[maxn], top[maxn], son[maxn], fa[maxn], size[maxn], dfn_num, dot[maxn], dep[maxn];
    int head[maxn], nxt[maxn << 1], ed[maxn << 1], cur;
    int sum[maxn << 2], tag[maxn << 2];

    inline void dfs_one(int now, int pre) {
        dep[now] = dep[pre] + 1;
        size[now] = 1;
        fa[now] = pre;
        for(int i = head[now]; i; i = nxt[i]) {
            if(ed[i] == pre) continue;
            dfs_one(ed[i], now);
            size[now] += size[ed[i]];
            if(size[ed[i]] > size[son[now]]) son[now] = ed[i];
        }
    }

    inline void dfs_two(int now, int pre, int front) {
        top[now] = front;
        dfn[now] = ++dfn_num;
        dot[dfn_num] = now;
        if(son[now]) dfs_two(son[now], now, front);
        for(int i = head[now]; i; i = nxt[i]) {
            if(ed[i] == pre || ed[i] == son[now]) continue;
            dfs_two(ed[i], now, ed[i]);
        }
    }

    inline void push_up(int x) { sum[x] = (sum[lson] + sum[rson]) % mod; }
    inline void build(int x, int l, int r) {
        if(l == r) { sum[x] = num[dot[l]] % mod; return; }
        int mid = (l + r) >> 1;
        build(lson, l, mid);
        build(rson, mid + 1, r);
        push_up(x);
    }

    inline void push_down(int x, int l, int r) {
        if(tag[x] == 0) return;
        int mid = (l + r) >> 1;
        add_mod(tag[lson], tag[x]);
        add_mod(tag[rson], tag[x]);
        add_mod(sum[lson], tag[x] * (mid - l + 1) % mod);
        add_mod(sum[rson], tag[x] * (r - mid) % mod);
        tag[x] = 0;
    }

    inline void update(int x, int l, int r, int from, int to, int temp) {
        if(l >= from && r <= to) {
            add_mod(tag[x], temp);
            add_mod(sum[x], temp * (r - l + 1));
            return;
        }
        int mid = (l + r) >> 1;
        push_down(x, l, r);
        if(from <= mid) update(lson, l, mid, from, to, temp);
        if(to > mid) update(rson, mid + 1, r, from, to, temp);
        push_up(x);
    }

    inline int get(int x, int l, int r, int from, int to) {
        if(l >= from && r <= to) return sum[x];
        int mid = (l + r) >> 1, res = 0;
        push_down(x, l, r);
        if(from <= mid) add_mod(res, get(lson, l, mid, from, to));
        if(to > mid) add_mod(res, get(rson, mid + 1, r, from, to));
        push_up(x);
        return res;
    }

    inline void add(int x, int y, int temp) {
        while(top[x] != top[y]) {
            if(dep[top[x]] < dep[top[y]]) swap(x, y);
            update(1, 1, total, dfn[top[x]], dfn[x], temp);
            x = fa[top[x]];
        }
        if(dep[x] < dep[y]) swap(x, y);
        update(1, 1, total, dfn[y], dfn[x], temp);
    }

    inline int query(int x, int y) {
        int res = 0;
        while(top[x] != top[y]) {
            if(dep[top[x]] < dep[top[y]]) swap(x, y);
            add_mod(res, get(1, 1, total, dfn[top[x]], dfn[x]));
            x = fa[top[x]];
        }
        if(dep[x] < dep[y]) swap(x, y);
        add_mod(res, get(1, 1, total, dfn[y], dfn[x]));
        return res;
    }

    inline void add_edge(int from, int to) {
        nxt[++cur] = head[from];
        head[from] = cur;
        ed[cur] = to;
    }

    inline void Main() {
        total = read_int(); test = read_int();
        root = read_int(); mod = read_int();
        rep(i, 1, total) num[i] = read_int();
        rep(i, 2, total) {
            u = read_int(); v = read_int();
            add_edge(u, v);
            add_edge(v, u);
        }
        dfs_one(root, 0);
        dfs_two(root, 0, root);
        build(1, 1, total);
        while(test--) {
            opt = read_int();
            if(opt == 1) { u = read_int(); v = read_int(); w = read_int(); add(u, v, w); }
            else if(opt == 2) { u = read_int(); v = read_int(); printf("%d\n", query(u, v)); }
            else if(opt == 3) { u = read_int(); v = read_int(); update(1, 1, total, dfn[u], dfn[u] + size[u] - 1, v); }
            else { u = read_int(); printf("%d\n", get(1, 1, total, dfn[u], dfn[u] + size[u] - 1)); }
        }
    }
}
namespace two_sat {
    const int maxn = 2e6 + 10;

    int total, test, a, b, c, d, u, v, w, opt;
    int nxt[maxn << 1], head[maxn << 1], ed[maxn << 1], cur;
    int dfn[maxn << 1], low[maxn << 1], dfn_num, col[maxn << 1], col_num;
    int stack[maxn << 1], top;
    bool jud[maxn << 1];

    inline void tarjan(int now, int pre) {
        dfn[now] = low[now] = ++dfn_num;
        stack[++top] = now;
        jud[now] = true;
        for(int i = head[now]; i; i = nxt[i]) {
            if(ed[i] == pre) continue;
            if(!dfn[ed[i]]) {
                tarjan(ed[i], now);
                low[now] = min(low[now], low[ed[i]]);
            } else if(jud[ed[i]]) low[now] = min(low[now], dfn[ed[i]]);
        }
        if(low[now] == dfn[now]) {
            col[now] = ++col_num;
            jud[now] = false;
            while(stack[top] != now) {
                jud[stack[top]] = false;
                col[stack[top]] = col_num;
                top--;
            }
            top--;
        }
    }

    inline void add_edge(int from, int to) {
        nxt[++cur] = head[from];
        head[from] = cur;
        ed[cur] = to;
    }

    inline void Main() {
        total = read_int();
        test = read_int();
        rep(i, 1, test) {
            a = read_int(); b = read_int();
            c = read_int(); d = read_int();
            add_edge(a + (b ^ 1) * total, c + d * total);
            add_edge(c + (d ^ 1) * total, a + b * total);
        }
        rep(i, 1, (total << 1)) 
            if(!dfn[i]) tarjan(i, 0);
        bool flag = true;
        rep(i, 1, total) 
            if(col[i] == col[i + total]) {
                printf("IMPOSSIBLE\n");
                exit(0);
            }
        printf("POSSIBLE\n");
        rep(i, 1, total) 
            printf("%d ", col[i] > col[i + total]);
    }
}

namespace ex_bsgs {
    ll a, b, p, k, limit, d, now, c, ans;
    bool jud;

    unordered_map<ll,ll> cube;

    inline ll gcd(ll x, ll y) {
        return !y ? x : gcd(y, x % y);
    }

    inline ll fast(ll x, ll y, ll p) {
        ll res = 1, step = x % p;
        while(y) {
            if(y & 1) res = res * step % p;
            step = step * step % p; 
            y >>= 1;
        }
        return res % p;
    }

    inline void Main() {
        while(scanf("%lld %lld %lld", &a, &p, &b) && (a || b || p)) {
            jud = false;
            cube.clear();
            c = 1, d = gcd(a, p), k = 0;
            if(b == 1) { printf("0\n"); continue; }
            while(d != 1) {
                if(b % d) {
                    printf("No Solution\n");
                    jud = true;break;
                }
                b /= d; p /= d; c = c * (a / d) % p; k++; d = gcd(a, p);
                if(b == c) {
                    printf("%lld\n", k);
                    jud = true;
                    break;
                }
            }
            if(jud) continue;
            limit = ceil(sqrt(p));
            now = b;
            for(int i = 0; i <= limit; i++) {
                cube[now] = i + 1;
                now = now * a % p;
            }
            ll stan = fast(a, limit, p);
            now = c; ans = -1;
            for(int i = 1; i <= limit; i++) {
                now = now * stan % p;
                if(cube[now]) {
                    ans = i * limit - cube[now] + 1 + k;
                    break;
                }
            }
            if(ans == -1) printf("No Solution\n");
            else printf("%lld\n", ans);
        } 
    }
}

namespace lucas {
	const ll maxn = 1e5 + 10;
	
	ll fac[maxn], inv_fac[maxn];
	ll test, u, v, w, opt, mod;
	
	inline ll c(ll n, ll m) {
		if(n < m) return 0;
		else return fac[n] * inv_fac[m] % mod * inv_fac[n - m] % mod;
	}
	
	inline ll solve(ll n, ll m) {
		if(!m) return 1;
		return c(n % mod, m % mod) * solve(n / mod, m / mod) % mod;
	}
	
	inline ll fast(ll a,ll b) {
		ll res = 1;
		while(b) {
			if(b & 1) res = res * a % mod;
			a = a * a % mod;
			b >>= 1;
		}
		return res % mod;
	}
	
	inline void Main() {
		test = read_ll();
		while(test--) {
			u = read_ll();
			v = read_ll();
			mod = read_ll();
			fac[0] = 1;
			rep(i, 1, mod - 1) fac[i] = fac[i - 1] * i % mod; 
			inv_fac[mod - 1] = fast(fac[mod - 1], mod - 2);
			per(i, mod - 2, 0) inv_fac[i] = inv_fac[i + 1] * (i + 1) % mod;
			printf("%lld\n", solve(u + v, u));
		}
	}
}


signed main() {
    // file();
    // ios::sync_with_stdio(false);
    // srand(time(NULL));
	two_sat::Main();
    // fclose(stdin);
    // fclose(stdout);
    // system("pause");
    return 0;
}