模板记录

#include <cstdio>
#include <cstring>
#include <iostream>
#include <ctime>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define pb push_back
#define pf push_front
#define wa std::cerr << "----WARN----" << std::endl;
#define debug(x) std::cout << #x << ':' << x << std::endl;
#define pii pair<int, int>
#define mp(a, b) make_pair(a, b)
#define fr first
#define sc second
#define PI acos(-1)

typedef long long ll;

const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1000000007;


/*
并查集模板
const int N = 10005;

int fa[N];

void initial(int n){
    for(int i=1;i<=n;i++){
        fa[i]=i;
    }
}

int find(int x){
    int fx,t;

    fx=x;
    while(fx!=fa[fx]){
        fx = fa[fx];
    }
    while(x!=fx){
        t = fa[x];
        fa[x] = fx;
        x = t;
    }
    return fx;
}

void merge(int x,int y){
    int fx,fy;

    fx = find(x);
    fy = find(y);
    if(fx!=fy){
        fa[fx] = fy;
    }
}
*/



/*
SPFA模版
const int N = 1005;
const int M = 2005;

struct Node{
    int v;
    int w;
    int next;
};

int dis[N],last[N],tot;
Node a[M<<1];
bool vis[N];

void add(int u, int v, int w){
    tot++;
    a[tot].v = v;
    a[tot].w = w;
    a[tot].next = last[u];
    last[u] = tot;
}

void spfa(int s){
    queue<int> q;
    int u,v,w;

    memset(dis,0x3f,sizeof(dis));
    memset(vis, false, sizeof(vis));

    dis[s] = 0;
    q.push(s);
    vis[s] = true;

    while(!q.empty()){
        u = q.front();
        q.pop();

        vis[u] = false;

        for(int i=last[u];i>0;i=a[i].next){
            v = a[i].v;
            w = a[i].w;

            if(dis[u]+w<dis[v]){
                dis[v] = dis[u] + w;

                if(vis[v]==false){
                    q.push(v);
                    vis[v] = true;
                }
            }
        }
    }
}

int main(){
    int m,n,u,v,w;

    scanf("%d%d",&m,&n);
    memset(last, 0, sizeof(last));
    tot=0;

    for(int i=0;i<m;i++){
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
        add(v,u,w); 
    }

    spfa(n);

    printf("%d\n", dis[1]);

    return 0;
}
*/


/*
Dijsktra模版

const int N = 1005;
const int M = 2005;

struct Edge{
    int v;
    int w;
    int next;
};

struct Node{
    int pos;
    int dis;

    Node(){
    }

    Node(int pos, int dis):pos(pos),dis(dis){
    }

    bool operator < (const Node &x) const{
        return x.dis < dis; //这里可以调整大小号，或者调整x.dis和dis的顺序实现大小根堆 
    }
};

int dis[N], last[N], tot;
Edge a[M<<1];
bool vis[N];

void add(int u, int v, int w){
    tot++;
    a[tot].v = v;
    a[tot].w = w;
    a[tot].next = last[u];
    last[u] = tot;
}

void dijsktra(int s){
    //没有后面两个参数，默认使用vector作为容器，比较方式默认使用operator<，参照Node中说明 
    priority_queue<Node> q; 
    Node nd;
    int u,v,w;

    memset(vis, false, sizeof(vis));
    memset(dis, 0x3f, sizeof(dis));

    q.push(Node(s, 0));
    dis[s] = 0;
    while(!q.empty()){
        nd = q.top();
        q.pop();

        u = nd.pos;
        if(vis[u]==true){
            continue;
        }

        vis[u] = true;
        for(int i=last[u];i>0;i=a[i].next){
            v = a[i].v;
            w = a[i].w;
            if(dis[u]+w<dis[v]){
                dis[v] = dis[u] + w;
                if(vis[v]==false){
                    q.push(Node(v, dis[v]));
                }
            } 
        }
    }
}

int main(){
    int n,m;
    int u,v,w;

    scanf("%d%d", &m, &n);

    memset(last, 0, sizeof(last));
    tot = 0;
    for(int i=0;i<m;i++){
        scanf("%d%d%d", &u, &v, &w);
        add(u, v, w);
        add(v, u, w);
    }

    dijsktra(n);

    printf("%d\n", dis[1]);

    return 0;
}
*/

/*
int gcd(int a, int b)  // 欧几里得算法
{
    return b ? gcd(b, a % b) : a;
}

*/


/*线段树区间更新模板

int tree[N<<2],mark[N<<2];
int a[N];

void build(int root, int left, int right){
    if(left==right){
        tree[root]=a[left];
        mark[root] = 0;
        return;
    }   

    int mid,rt;
    rt = root << 1;
    mid = (left+right)>>1;

    build(rt, left, mid);
    build(rt+1, mid+1, right);

    tree[root] = tree[rt] + tree[rt+1];
}

void pushdown(int root, int left, int right){
    int mid,rt;
    rt = root << 1;
    mid = (left+right)>>1;

    mark[rt] += mark[root];
    mark[rt+1] += mark[root];
    tree[rt] += mark[root] * (mid - left + 1);
    tree[rt+1] += mark[root] * (right - mid);

    mark[root] = 0;
}

void update(int root, int left, int right, int uleft, int uright, int val){
    if(uleft<=left && right<=uright){
        tree[root] += (right-lef+1)*val;
        mark[root] += val;

        return;
    }

    if(mark[root]>0){
        pushdown(root, left, right);
    }

    int mid,rt;
    rt = root << 1;
    mid = (left+right)>>1;

    if(uleft<=mid){
        update(rt, left, mid, uleft, uright, val);
    }

    if(uright>mid){
        update(rt+1, mid+1, right, uleft, uright, val);
    }

    tree[root] = tree[rt] + tree[rt+1];
}

int query(int root, int left, int right, int qleft, int qright){
    if(qleft<=left && right<=qright){
        return tree[root];
    }

    if(mark[root]>0){
        pushdown(root, left, right);
    }

    int mid,rt,ans;
    rt = root << 1;
    mid = (left+right)>>1;

    ans = 0;
    if(qleft<=mid){
        ans += query(rt, left, mid, qleft, qright);
    }

    if(qright>mid){
        ans += query(rt+1, mid+1, right, qleft, qright);
    }

    return ans;
}
*/



//读字符串
    /*
    getchar();//吃回车符 
    for(int i = 0; i < n; i++){
        j = 0;
        ch = getchar(); 
        while(ch!='\n'){
            a[i][j]= ch;
            j++;
            ch = getchar();
        }
    }
    */


//递归快速幂（对大素数取模） 
ll qpow(ll a, ll n)
{
    if (n == 0)
        return 1;
    else if (n % 2 == 1)
        return qpow(a, n - 1) * a % MOD;
    else
    {
        ll temp = qpow(a, n / 2) % MOD;
        return temp * temp % MOD;
    }
}
//非递归快速幂1
int quick_power(int a, int k, int p)  // 求a^k mod p
{
    int res = 1 % p;
    while (k)
    {
        if (k & 1) res = (LL)res * a % p;
        a = (ll)a * a % p;
        k >>= 1;
    }
    return res;
}
//非递归快速幂2
int qpow(int a, int n){
    int ans = 1;
    while(n){
        if(n&1)        //如果n的当前末位为1
            ans *= a;  //ans乘上当前的a
        a *= a;        //a自乘
        n >>= 1;       //n往右移一位
    }
    return ans;
}

//矩阵快速幂 
Matrix matrixmul(Matrix a,Matrix b)
{
       int i,j,k;
       Matrix c;
       for (i = 0 ; i < MAX; i++)
           for (j = 0; j < MAX;j++)
             {
                 c.m[i][j] = 0;
                 for (k = 0; k < MAX; k++)
                     c.m[i][j] += (a.m[i][k] * b.m[k][j])%MOD;
                 c.m[i][j] %= MOD;
             }
       return c;
}

Matrix quickpow(long long n)
{
       Matrix m = P, b = I;
       while (n >= 1)
       {
             if (n & 1)
                b = matrixmul(b,m);
             n = n >> 1;
             m = matrixmul(m,m);
       }
       return b;
}

int main(){







    return 0;
}