#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
#define fi first
#define se second
const int maxn = 1e5+5;

mt19937 rng(69);
int random_number() {
    uniform_int_distribution<int> dist(1, 1'000'000);
    return dist(rng);
}
void checking() {
    int A, B, a, b;
    while (true) {
        a = random_number();
        b = random_number();
        A = full::solve(a, b);
        B = trau::solve(a, b);
        if (A != B) {
            cout << "WA!" << endl;
            cout << a << " " << b << endl;
            cout << A << " " << B << endl;
            return;
        }
        cout << "AC" << endl;
    }
}

ll binpow(ll a, ll b, ll mod) {
    ll res = 1;
    while (b > 0) {
        if (b & 1) {
            res = (res * a) % mod;
        }
        a = (a * a) % mod;
        b >>= 1;
    }
    return res;
}

ll binmul(ll a, ll b, ll mod) {
    ll res = 0;
    a %= mod;
    while (b > 0) {
        if (b & 1) {
            res = (res + a) % mod;
        }
        a = (a<<1) % mod;
        b >>= 1;
    }
    return res;
}

vector<int> a[maxn];  // Đồ thị không trọng số
vector<pair<int, ll>> adj[maxn];  // Đồ thị có trọng số

//BFS
void bfs_tom(int s) {
    queue<int> q;
    q.push(s);
    visited[s]=true;
    dtom[s]=0;

    while(!q.empty()){
        int u = q.front();
        q.pop();
        for(auto v : graph[u]){
            if(!visited[v]){
                dtom[v]=dtom[u]+1;
                visited[v]=true;
                q.push(v);
            }
        }
    }
}

//TRIE
int n,m,mark;
string s;

struct node{
    int ch[26];
    bool isEnd = false;
};
node trie[maxn*5];

void add(const string &s){
    int x=0;
    for(auto c : s){
        int idx = c-'a';
        if(trie[x].ch[idx]==0)  trie[x].ch[idx]=++mark;
        x = trie[x].ch[idx];
    }
    trie[x].isEnd=true;
}

bool check(const string &s){
    int x = 0;
    for(const char &c:s){
        int idx = c-'a';
        if(trie[x].ch[idx]==0)  return false;
        x=trie[x].ch[idx];
    }
    return trie[x].isEnd;
}

//DIJKSTRA
int n,m;
vector<pair<int,int>> a[maxn];

struct node{
    int w,x;
    bool operator<(const node& other) const{
        return w > other.w;
    }
};

priority_queue<node> q;

void dijkstra(int start){
    vector<int> dist(n+1,INF);
    vector<int> par(n+1,-1);
    vector<int> path;
    q.push({0,1});
    dist[start]=0;
    while(!q.empty()){
        int w = q.top().w;
        int x = q.top().x;
        q.pop();

        if(w > dist[x]) continue;

        for(auto it : a[x]){
            int u = it.fi;
            int W = it.se;

            if(dist[u] > dist[x]+W){
                dist[u]= dist[x] +W;
                par[u]=x;
                q.push({dist[u],u});
            }
        }
    }

    if (dist[n] == INF) {
        cout << -1 << "\n";
        return;
    }
    cout << dist[n] << endl;

    for(int i=n;i!=-1;i=par[i]){
        path.pb(i);
    }
    reverse(path.begin(),path.end());
    for(auto x : path)  cout << x << " ";
    cout << "\n";
}

//BIGNUM
bool ss(string a,string b)
{
    while(a.length()<b.length())a='0'+a;
    while(b.length()<a.length())b='0'+b;
    if(a>b)return true;
    else return false;
}

string congsl(string a, string b)
{
    string c;
    long long r=0,d=0;
    while (a.length()>b.length()) b='0'+b;
    while (a.length()<b.length()) a='0'+a;
    for (int i=a.length()-1; i>=0; i--)
    {
        long long sum=(a[i]-'0')+(b[i]-'0')+d;
        r=sum%10;
        d=sum/10;
        c=char(r+'0')+c;
    }
    if (d>0) c=char(d+'0')+c;
    return c;
}
string trusl(string a, string b)
{
    string c;
    while (a.length()>b.length()) b='0'+b;
    while (a.length()<b.length()) a='0'+a;
    int count=0;
    if (a<b)
    {
        swap(a,b);
        count=1;
    }
    long long d=0;
    for (int i=a.length()-1; i>=0; i--)
    {
        long long hieu=(a[i]-'0')-(b[i]-'0')-d;
        if (hieu<0)
        {
            hieu+=10;
            d=1;
        }
        else d=0;
        c=char(hieu+'0')+c;
    }
    if (count==1 and c!="0") c='-'+c;
    while (c.length()>1 and c[0]=='0') c.erase(0,1);
    return c;
}

string nhansl(string a,string b){
    int m = a.size();
    int n = b.size();
    vector<int> res(m+n,0);

    for(int i=m-1;i>=0;i--){
        for(int j=n-1;j>=0;j--){
            ll nhan = (a[i]-'0')*(b[j]-'0');
            ll sum = nhan+res[i+j+1];
            res[i+j+1]=sum%10;
            res[i+j]+=sum/10;
        }
    }

    string s;
    for(int i : res){
        if(!(s.empty() && i==0)){
            s.push_back(i+'0');
        }
    }

    if(s.empty())   return "0";

    return s;
}

string chiasl(string a,string b)
{
    string t[11];
    int i,sl;
    string c,du;
    t[0]='0';
    for(i=1;i<=10;i++)t[i]=congsl(t[i-1],b);
    for(i=0;i<a.length();i++)
    {
        du=du+a[i];
        sl=0;
        while(ss(du,t[sl])==true)sl++;
        c=c+(char)(sl-1+48);
        du=trusl(du,t[sl-1]);
    }
    while(c[0]=='0'&&c.length()>1)c.erase(0,1);
    return c;
}

// SEGMENT TREE LAZY
const int maxn = 2e5+5;
ll a[N];
ll seg[4 * N];
ll lazy[4 * N];

void build(int x, int l, int r) {
    lazy[x] = 0;
    if (l == r) {
        seg[x] = a[l];
        return;
    }
    int m = (l + r) / 2;
    build(2 * x, l, m);
    build(2 * x + 1, m + 1, r);
    seg[x] = seg[2 * x] + seg[2 * x + 1];
    return;
}

void update_lazy(int x, int l, int r) {
    if (lazy[x] == 0) return;
    seg[x] += lazy[x] * (r - l + 1);
    if (l != r) {
        lazy[2 * x] += lazy[x];
        lazy[2 * x + 1] += lazy[x];
    }
    lazy[x] = 0;
    return;
}

void update(int x, int l, int r, int lo, int hi, ll val) {
    update_lazy(x, l, r);
    if (l > hi || r < lo) return;
    if (l >= lo && r <= hi) {
        lazy[x] += val;
        update_lazy(x, l, r);
        return;
    }
    int m = (l + r) / 2;
    update(2 * x, l, m, lo, hi, val);
    update(2 * x + 1, m + 1, r, lo, hi, val);
    seg[x] = seg[2 * x] + seg[2 * x + 1];
    return;
}

ll query(int x, int l, int r, int lo, int hi) {
    update_lazy(x, l, r);
    if (l > hi || r < lo) return 0;
    if (l >= lo && r <= hi) return seg[x];

    int m = (l + r) / 2;
    ll ans = query(2 * x, l, m, lo, hi) + query(2 * x + 1, m + 1, r, lo, hi);
    seg[x] = seg[2 * x] + seg[2 * x + 1];
    return ans;
}

// HASH
const int base = 31;
const ll mod = 1e9+7;
int hashstr[maxn], basepow[maxn];

void hashinit() {
    basepow[0] = 1;
    for (int i = 1; i < maxn; ++i)
        basepow[i] = (basepow[i-1] * base) % mod;
}

void create(const string &s) {
    hashstr[0] = 0;
    for (int i = 1; i <= s.size(); ++i)
        hashstr[i] = (hashstr[i-1] * base + s[i]-'a'+1) % mod;
}

ll getHash(int l, int r) {
    return ((hashstr[r] - hashstr[l - 1] * basepow[r - l + 1]) % mod +  mod) % mod;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}