#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 500005;

int n, m;
ll a[N];
struct Node{
    int l, r;
    ll sum, d;
}tr[N * 4];
ll gcd(ll a ,ll b){
    return b ? gcd(b, a % b) : a;
}
void pushup(Node &u, Node &l, Node &r){
    u.sum = l.sum + r.sum;
    u.d = gcd(l.d, r.d);
}
void pushup(int u){
    pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}
void build(int u, int l, int r){
    if(l == r){
        ll b = a[l] - a[l - 1];
        tr[u] = {l, r, b, b};
    }
    else{
        tr[u] = {l, r};
        int mid = l + r >> 1;
        build(u << 1, l, mid); build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}
void modify(int u, int x, ll v){ // 单点修改
    if(tr[u].l == x && tr[u].r == x) {
        ll b = tr[u].sum + v;
        tr[u] = {x, x, b, b};
    }
    else{
        int mid = tr[u].l + tr[u].r >> 1;
        if(x <= mid) modify(u << 1, x, v);
        else modify(u << 1 | 1, x, v);
        pushup(u);
    }
}
Node query(int u, int l, int r){
    if(tr[u].l >= l && tr[u].r <= r) return tr[u];
    else{
        int mid = tr[u].l + tr[u].r >> 1;
        if(r <= mid) return query(u << 1, l, r);
        else if(l >= mid + 1) return query(u << 1 | 1, l, r);
        else{
            Node left = query(u << 1, l, r);
            Node right = query(u << 1 | 1, l, r);
            Node res;
            pushup(res, left, right);
            return res;
        }
    }
}
int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++ ) scanf("%lld", &a[i]);
    build(1, 1, n);
    char op[2];
    while(m -- ){
        scanf("%s", op);
        if(*op == 'Q'){
            int l, r;
            scanf("%d%d", &l, &r);
            Node left = query(1, 1, l);
            Node right = {0, 0, 0, 0}; // b_i = a_i - a_i-1
            if(l + 1 <= r) right = query(1, l + 1, r); // a_l = sum(b_1...b_l)
            printf("%lld\n", abs(gcd(left.sum, right.d))); // gcd(a_l...a_r) = gcd(a_l, b_l+1...b_r)
        }
        else{
            int l, r;
            ll d;
            scanf("%d%d%lld", &l, &r, &d);
            modify(1, l, d);
            if(r + 1 <= n) modify(1, r + 1, -d); // 最后一个位置不用改
        }
    }
    return 0;
}

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int N = 500005;
int n, m;
int w[N];
struct Node{
    int l, r;
    int sum, lmax, rmax, tmax;
}tr[N * 4];


void pushup(Node &u, Node &l, Node &r){
    u.sum = l.sum + r.sum;
    u.lmax = max(l.sum + r.lmax, l.lmax);
    u.rmax = max(r.sum + l.rmax, r.rmax);
    u.tmax = max(l.tmax, r.tmax);
    u.tmax = max(u.tmax, l.rmax + r.lmax);
}
void pushup(int u){
    pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}
void build(int u, int l, int r){
    if(l == r) tr[u] = {l, r, w[r], w[r], w[r], w[r]};
    else{
        tr[u] = {l, r};
        int mid = l + r >> 1;
        build(u << 1, l, mid); build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}
void modify(int u, int x, int v){ // 单点修改
    if(tr[u].l == x && tr[u].r == x) tr[u] = {x, x, v, v, v, v};
    else{
        int mid = tr[u].l + tr[u].r >> 1;
        if(x <= mid) modify(u << 1, x, v);
        else modify(u << 1 | 1, x, v);
        pushup(u);
    }
}
Node query(int u, int l, int r){
    if(tr[u].l >= l && tr[u].r <= r) return tr[u];
    else{
        int mid = tr[u].l + tr[u].r >> 1;
        if(r <= mid) return query(u << 1, l, r);
        else if(l >= mid + 1) return query(u << 1 | 1, l, r);
        else{
            Node left = query(u << 1, l ,r);
            Node right = query(u << 1 | 1, l, r);
            Node res;
            pushup(res, left, right);
            return res;
        }
    }
}

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
    build(1, 1, n);
    while(m -- ){
        int k ,x, y;
        scanf("%d%d%d", &k, &x, &y);
        if(k == 1){ // 查询
            if(x > y) swap(x, y);
            Node res = query(1, x, y);
            printf("%d\n", res.tmax);
        }
        else {
            modify(1, x, y);
        }
    }
    return 0;
}

// Q L 询问后L个数最大值
// A t 插入数字（t + a） % p, 其中a是上次查询值（初始为0）
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int N = 200005;
int m, p;
struct Node{
    int l, r;
    int v; // max
}tr[N * 4];

void build(int u, int l, int r){ // 建树|编号，左右端点
    tr[u] = {l ,r};
    if(l == r) return;
    int mid = l + r  >> 1;
    build(u << 1, l, mid); build(u << 1 | 1, mid + 1, r);
}
void pushup(int u){
    tr[u].v = max(tr[u << 1].v, tr[u << 1 | 1].v);
}
int query(int u, int l, int r){
    if(tr[u].l >= l && tr[u].r <= r) return tr[u].v;

    int mid = tr[u].l + tr[u].r >> 1; // 树中点
    int v = 0;
    if(l <= mid) v = query(u << 1, l, r); // 包含左边
    if(r >= mid + 1) v = max(v, query(u << 1 | 1, l, r)); // 包含右边
    return v;

}
void modify(int u, int x, int v){
    if(tr[u].l == x && tr[u].r == x) tr[u].v = v;
    else{
        int mid = tr[u].l + tr[u].r >> 1;
        if(x <= mid) modify(u << 1, x, v);
        else modify(u << 1 | 1, x, v);
        pushup(u);
    }
}
int main(){
    int last = 0, n = 0;
    scanf("%d%d", &m, &p);
    build(1, 1, m);
    char op[2];
    int x;
    while(m -- ){
        scanf("%s%d", op, &x);
        if(op[0] == 'Q'){
            last = query(1, n - x + 1, n);
            printf("%d\n", last);
        }
        else{
            n ++;
            modify(1, n, (x + last) % p);
        }
    }
    return 0;
}

#include<bits/stdc++.h>

using namespace std;

const int N = 2010, M = 10010;

int n, m;
int h[N], w[M], e[M], ne[M], idx;
int dist[N], cnt[N];
bool st[N];

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

bool spfa()
{
    queue<int> q;

    for (int i = 1; i <= n; i ++ )
    {
        st[i] = true;
        q.push(i);
    }

    while (q.size())
    {
        int t = q.front();
        q.pop();

        st[t] = false;

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;

                if (cnt[j] >= n) return true;
                if (!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    return false;
}

int main()
{
    scanf("%d%d", &n, &m);

    memset(h, -1, sizeof h);

    while (m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }

    if (spfa()) puts("Yes");
    else puts("No");

    return 0;
}

#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int N = 1e5 + 5;
int n, m, q[N] ,dist[N], h[N], e[N], ne[N], w[N], idx;
bool st[N];

int add(int a, int b, int c){
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx ++ ;
}

int spfa(){
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0; st[1] = true;
    int hh = 0, tt = -1;
    q[ ++ tt] = 1;
    while(hh <= tt){
        int t = q[hh ++ ];
        st[t] = false;
        for(int i = h[t]; i != -1; i = ne[i]){
            int j = e[i];
            if(dist[j] > dist[t] + w[i]){
                dist[j] = dist[t] + w[i];
                if(!st[j]) q[ ++ tt] = j, st[j] = true;
            }
        }
    }
    return dist[n] == 0x3f3f3f3f ? -1 : dist[n];
}

int main(){
    memset(h, -1, sizeof h);
    cin >> n >> m;
    while(m -- ){
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }
    int t = spfa();
    if(t == -1) puts("impossible");
    else printf("%d", t);

    return 0;
}

#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int N = 505, M = 10010;
int n, m, k, dist[N], backup[N];
struct Edge{
    int a, b, w;
}edges[M];

int bellman_ford(){
    memset(dist, 0x3f, sizeof dist); 
    dist[1] = 0;
    for(int i = 0; i < k; i ++ ){
        memcpy(backup, dist, sizeof dist);
        for(int j = 0; j < m; j ++ ){
            Edge e = edges[j];
            dist[e.b] = min(dist[e.b], e.w + backup[e.a]);
        }
    }
    if(dist[n] > 0x3f3f3f3f / 2) return -1;
    return dist[n];
}

int main(){
    cin >> n >> m >> k;
    for(int i = 0; i < m; i ++ ){
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        edges[i] = {a, b, w};
    }
    int t = bellman_ford();
    if(t == -1) puts("impossible");
    else printf("%d", t);
    return 0;
}

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

const int N=1e5+10;
int h[N];   //堆
int ph[N];  //存放第k个插入点的下标
int hp[N];  //存放堆中点的插入次序
int cur_size;   //size 记录的是堆当前的数据多少

//这个交换过程其实有那么些绕 但关键是理解 如果hp[u]=k 则ph[k]=u 的映射关系
//之所以要进行这样的操作是因为 经过一系列操作 堆中的元素并不会保持原有的插入顺序
//从而我们需要对应到原先第K个堆中元素
//如果理解这个原理 那么就能明白其实三步交换的顺序是可以互换 
//h,hp,ph之间两两存在映射关系 所以交换顺序的不同对结果并不会产生影响
void heap_swap(int u,int v)
{   
    swap(h[u],h[v]); 
     swap(hp[u],hp[v]);     
     swap(ph[hp[u]],ph[hp[v]]);            

}

void down(int u)
{
    int t=u;
    if(u*2<=cur_size&&h[t]>h[u*2]) t=u*2;
    if(u*2+1<=cur_size&&h[t]>h[u*2+1])  t=u*2+1;
    if(u!=t)
    {
        heap_swap(u,t);
        down(t);
    }
}
void up(int u)
{
    if(u/2>0&&h[u]<h[u/2]) 
    {
        heap_swap(u,u/2);
        up(u>>1);
    }
}

int main()
{
    int n;
    cin>>n;
    int m=0;      //m用来记录插入的数的个数
                //注意m的意义与cur_size是不同的 cur_size是记录堆中当前数据的多少
                //对应上文 m即是hp中应该存的值
    while(n--)
    {
        string op;
        int k,x;
        cin>>op;
        if(op=="I")
        {
            cin>>x;
            m++;
            h[++cur_size]=x;
            ph[m]=cur_size;
            hp[cur_size]=m;
            //down(size);
            up(cur_size);
        }
        else if(op=="PM")    cout<<h[1]<<endl;
        else if(op=="DM")
        {
            heap_swap(1,cur_size);
            cur_size--;
            down(1);
        }
        else if(op=="D")
        {
            cin>>k;
            int u=ph[k];                //这里一定要用u=ph[k]保存第k个插入点的下标
            heap_swap(u,cur_size);          //因为在此处heap_swap操作后ph[k]的值已经发生 
            cur_size--;                    //如果在up,down操作中仍然使用ph[k]作为参数就会发生错误
            up(u);
           down(u);
        }
        else if(op=="C")
        {
            cin>>k>>x;
            h[ph[k]]=x;                 //此处由于未涉及heap_swap操作且下面的up、down操作只会发生一个所以
            down(ph[k]);                //所以可直接传入ph[k]作为参数
            up(ph[k]);
        }

    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 50005; // 0 吃 1

int n, k, p[N], d[N], ans;
int find(int x){
    if(p[x] != x){
        int t = find(p[x]); // 防止p[x]被直接更新成
        d[x] += d[p[x]];
        p[x] = t;
    }
    return p[x];
}
int main(){
    cin >> n >> k;
    for(int i = 1; i <= n; i ++ ) p[i] = i;

    while(k -- ){
        int t, x, y;
        scanf("%d%d%d", &t, &x, &y); // 1（同类) A B; 2 捕食者 被捕食者
        if(x > n || y > n) {ans ++ ; continue;}
        int px = find(x), py = find(y);
        if(t == 1){
            if(px == py && (d[x] - d[y]) % 3) ans ++ ;
            else if(px != py){
                p[px] = py;
                d[px] = d[y] - d[x];
            }
        }
        else {
            if(px == py && (d[x] - d[y] - 1) % 3) ans ++ ;
            else if(px != py){
                p[px] = py;
                d[px] = d[y] - d[x] + 1;
            }
        }
    }
    cout << ans;
    return 0;
}

// 线性表相关

bool ListInsert(Sqlist &L, int i, ElemType e){ // 插入
    if(i < 1 || i > L.length + 1 || L.length >= MaxSize) return 0; // +1
    for(int j = L.length; j >= i; j -- ) L.data[j] = L.data[j - 1]; // 后移
    L.data[i - 1] = e; L.length ++; // 插入，表长++
    return 1;
}

bool ListDelete(Sqlist &L, int i, ElemType &e){ // 删除
    if(i < 1 || i > L.length || L.length >= MaxSize) return 0; // 无+1
    L.data[i - 1] = e;
    for(int j = i; j < L.length; j ++ ) L.data[j - 1] = L.data[j]; // 前移
    L.length -- ;
    return 1;
}

int LocateElem(SqList L, ElemType e){ // 查找
    for(int i = 0; i < L.length; i ++ )
        if(L.data[i] == e) return i + 1;
    return 0;
}

// 二叉排序树

BSTNode *BST_Search(BiTree T, ElemType key){ // 非递归，查找
    while(T != NULL && key != T -> data){
        if(key < T -> data) T = T -> lchild;
        else T = T -> rchild;
    }
    return T;
}

int BST_Insert(BiTree &T, KeyType k){ // 插入
    if(T == NULL){
        T = (BiTree)malloc(sizeof(BSTNode));
        T -> data = k;
        T -> lchild = T -> rchild = NULL;
        return 1; // 插入成功
    }
    else if(k == T -> data) return 0; // 存在
    else if(k < T -> data) return BST_Insert(T -> lchild, k);
    else return BST_Insert(T -> rchild, k);
}

// 删除
// 删除节点仅有一个子树时，直接用子树填上去
// 如果左右树都不空，*用右边子树中序遍历的第一个填上去