#define ll long long

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N = 111, M = 2511;

int n, m, k; ll d[N][N], f[N][N];

struct node {

    ll u, v, t;

}edge[M];

void floyd() {

    for (int k = 1; k <= n; k++) for (int i = 1; i <= n; i++)

        for (int j = 1; j <= n; j++) d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

    memcpy(f, d, sizeof f);
}

void mul(ll c[][N], ll a[][N], ll b[][N]) {

    ll temp[N][N];

    memset(temp, 0x3f, sizeof temp);

    for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++)

        for (int k = 1; k <= n; k++) temp[i][j] = min(temp[i][j], a[i][k] + b[k][j]);

    memcpy(c, temp, sizeof temp);
}

ll qmi() {

    int nk = k;

    while (nk) {

        if (nk & 1) mul(d, d, f);

        mul(f, f, f);

        nk >>= 1;
    }
    return d[1][n];
}

int main() {

    cin >> n >> m >> k;

    memset(d, 0x3f, sizeof d);

    for (int i = 1; i <= n; i++) d[i][i] = 0;

    for (int i = 0; i < m; i++) {

        ll u, v, t;

        cin >> u >> v >> t;

        edge[i] = { u,v,t };

        d[u][v] = min(t, d[u][v]);
    }

    floyd();

    for (int k = 0; k < m; k++) {

        ll u = edge[k].u, v = edge[k].v, t = edge[k].t;

        for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++)

            f[i][j] = min(f[i][j], d[i][u] + d[v][j] - t);
    }

    cout << qmi();

    return 0;
}

#define ll long long

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<map>

using namespace std;

const int N = 210;

int n, t, s, e, cnt, g[N][N], ans[N][N]; map<int, int> mp;

inline void mul(int c[][N], int a[][N], int b[][N]) {

    int temp[N][N];

    memset(temp, 0x3f, sizeof temp);

    for (int k = 1; k <= cnt; k++) for (int i = 1; i <= cnt; i++)

        for (int j = 1; j <= cnt; j++) temp[i][j] = min(temp[i][j], a[i][k] + b[k][j]);

    memcpy(c, temp, sizeof temp);
}

void qmi() {

    memset(ans, 0x3f, sizeof ans);

    for (int i = 1; i <= cnt; i++) ans[i][i] = 0;

    while (n) {

        if (n & 1) mul(ans, ans, g);

        mul(g, g, g);

        n >>= 1;
    }
}

int main() {

    cin >> n >> t >> s >> e;

    memset(g, 0x3f, sizeof g);

    if (!mp.count(s)) mp[s] = ++cnt;

    if (!mp.count(e)) mp[e] = ++cnt;

    s = mp[s], e = mp[e];

    for (int i = 0; i < t; i++) {

        int a, b, c;

        cin >> c >> a >> b;

        if (!mp.count(a)) mp[a] = ++cnt;

        if (!mp.count(b)) mp[b] = ++cnt;

        a = mp[a], b = mp[b];

        g[a][b] = g[b][a] = min(g[a][b], c);
    }

    qmi();

    cout << ans[s][e] << endl;

    return 0;
}

#define ll long long

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N = 4;

int n, m;

void mul(int c[][N], int a[][N], int b[][N]) {

    int t[N][N];

    memset(t, 0, sizeof t);

    for (int i = 0; i < N; i++) for (int j = 0; j < N; j++)

        for (int k = 0; k < N; k++) t[i][j] = (t[i][j] + (ll)a[i][k] * b[k][j]) % m;

    memcpy(c, t, sizeof t);
}

int main() {

    cin >> n >> m;

    // {fn, fn+1, sn, pn}
    // pn = n * sn - tn
    int f1[N][N] = { 1, 1, 1, 0 };

    int a[N][N] = { {0, 1, 0, 0},{1, 1, 1, 0},{0, 0, 1, 1},{0, 0, 0, 1}, };

    int k = n - 1;

    while (k) {

        if (k & 1) mul(f1, f1, a);  // f1 = f1 * a

        mul(a, a, a);  // a = a * a

        k >>= 1;
    }

    cout << (((ll)n * f1[0][2] - f1[0][3]) % m + m) % m << endl;

    return 0;
}

#define ll long long

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N = 3;

int n, m;

void mul(int c[], int a[], int b[][N]){

    int temp[N] = { 0 };

    for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) temp[i] = (temp[i] + (ll)a[j] * b[j][i]) % m;

    memcpy(c, temp, sizeof temp);
}

void mul(int c[][N], int a[][N], int b[][N]) {

    int temp[N][N] = { 0 };

    for (int i = 0; i < N; i++) for (int j = 0; j < N; j++)

        for (int k = 0; k < N; k++) temp[i][j] = (temp[i][j] + (ll)a[i][k] * b[k][j]) % m;

    memcpy(c, temp, sizeof temp);
}

int main() {

    cin >> n >> m;

    int f1[N] = { 1, 1, 1 };

    int a[N][N] = { {0, 1, 0}, {1, 1, 1}, {0, 0, 1} };

    n--;

    while (n) {

        if (n & 1) mul(f1, f1, a);  // res = res * a

        mul(a, a, a);  // a = a * a

        n >>= 1;
    }

    cout << f1[2] << endl;

    return 0;
}

#define ll long long

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N = 2e5 + 10; const ll INF = 0x7fffffffffffffff;

int arr[N],n, m;

struct Node {

    int l, r; ll minn, add;

}tr[N * 4];

void pushup(int u){

    tr[u].minn = min(tr[u << 1].minn, tr[u << 1 | 1].minn);
}

void pushdown(int u) {

    tr[u << 1].minn += tr[u].add; tr[u << 1].add += tr[u].add;

    tr[u << 1 | 1].minn += tr[u].add; tr[u << 1 | 1].add += tr[u].add;

    tr[u].add = 0;
}

void build(int u, int l, int r) {

    tr[u].l = l, tr[u].r = r;

    if (l == r) {

        tr[u].minn = arr[l];

        return;
    }

    int mid = l + r >> 1;

    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);

    pushup(u);
}

void modify(int u, int l, int r, int x) {

    if (tr[u].l >= l && tr[u].r <= r) {

        tr[u].minn += x;

        tr[u].add += x;

        return;
    }

    pushdown(u);

    int mid = tr[u].l + tr[u].r >> 1;

    if (l <= mid) modify(u << 1, l, r, x);

    if (r > mid) modify(u << 1 | 1, l, r, x);

    pushup(u);
}

ll query(int u, int l, int r) {

    if (tr[u].l >= l && tr[u].r <= r) return tr[u].minn;

    pushdown(u);

    int mid = tr[u].l + tr[u].r >> 1;

    ll ans = INF;

    if (l <= mid) ans = query(u << 1, l, r);

    if (r > mid) ans = min(ans, query(u << 1 | 1, l, r));

    return ans;
}

int main() {

    cin >> n;

    for (int i = 0; i < n; i++) cin >> arr[i];

    build(1, 0, n - 1);

    cin >> m;

    for (int i = 0; i < m; i++) {

        int l, r, d; char c;

        scanf("%d %d%c", &l, &r, &c);

        if (c == '\n') {

            if (l <= r) cout << query(1, l, r) << endl;

            else cout << min(query(1, l, n - 1), query(1, 0, r)) << endl;
        }
        else {

            cin >> d;

            if (l <= r) modify(1, l, r, d);

            else modify(1, l, n - 1, d), modify(1, 0, r, d);
        }
    }
    return 0;
}

#define ll long long

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N = 1e5 + 11;

int n, m, w[N];

struct Node{

    int l, r; ll sum, add;

}tr[N * 4];

void pushup(int u){

    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}

void pushdown(int u) {

    auto& root = tr[u], & left = tr[u << 1], & right = tr[u << 1 | 1];

    if (root.add) {

        left.add += root.add, left.sum += (ll)(left.r - left.l + 1) * root.add;

        right.add += root.add, right.sum += (ll)(right.r - right.l + 1) * root.add;

        root.add = 0;
    }
}

void build(int u, int l, int r) {

    if (l == r) tr[u] = { l, r, w[r], 0 };

    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 l, int r, int d) {

    if (tr[u].l >= l && tr[u].r <= r) {

        tr[u].sum += (ll)(tr[u].r - tr[u].l + 1) * d;

        tr[u].add += d;
    }
    else {

        pushdown(u);

        int mid = tr[u].l + tr[u].r >> 1;

        if (l <= mid) modify(u << 1, l, r, d);

        if (r > mid) modify(u << 1 | 1, l, r, d);

        pushup(u);
    }
}

ll query(int u, int l, int r) {

    if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum;

    pushdown(u);

    int mid = tr[u].l + tr[u].r >> 1; ll sum = 0;

    if (l <= mid) sum = query(u << 1, l, r);

    if (r > mid) sum += query(u << 1 | 1, l, r);

    return sum;
}

int main() {

    cin >> n >> m;

    for (int i = 1; i <= n; i++) cin >> w[i];

    build(1, 1, n);

    for (int i = 0; i < m; i++) {

        int l, r, d; char op[2];

        cin >> op >> l >> r;

        if (*op == 'C') {

            cin >> d;

            modify(1, l, r, d);
        }
        else cout << query(1, l, r) << endl;
    }
    return 0;
}

#define ll long long

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N = 2e5 + 11;

int m, p;

struct Node{

    int l, r, v; // 区间[l, r]中的最大值

}tr[N * 4];

void pushup(int u) { // 由子节点的信息，来计算父节点的信息

    tr[u].v = max(tr[u << 1].v, tr[u << 1 | 1].v);
}

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);
}

int query(int u, int l, int r){

    if (tr[u].l >= l && tr[u].r <= r) return tr[u].v;   // 树中节点，已经被完全包含在[l, r]中了

    int mid = tr[u].l + tr[u].r >> 1, v = 0;

    if (l <= mid) v = query(u << 1, l, r);

    if (r > mid) 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 n = 0, last = 0, x; char op[2];

    cin >> m >> p;

    build(1, 1, m);

    for (int i = 0; i < m; i++) {

        cin >> op >> x;

        if (*op == 'Q') {

            last = query(1, n - x + 1, n);

            cout << last << endl;
        }
        else {

            modify(1, n + 1, ((ll)last + x) % p);

            n++;
        }
    }

    return 0;
}

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N = 1511;

int n, h[N], e[N], ne[N], idx, f[N][2]; bool st[N];

void add(int a, int b){

    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void dfs(int u){

    f[u][0] = 0, f[u][1] = 1;

    for (int i = h[u]; ~i; i = ne[i]){

        int j = e[i];

        dfs(j);

        f[u][0] += f[j][1] ;

        f[u][1] += min(f[j][0], f[j][1]);
    }
}

int main() {

    while (scanf("%d", &n) != EOF) {

        memset(h, -1, sizeof h);

        idx = 0;

        memset(st, 0, sizeof st);

        for (int i = 0; i < n; i++) {

            int id, cnt;

            scanf("%d:(%d)", &id, &cnt);

            for (int i = 0; i < cnt; i++) {

                int ver;

                cin >> ver;

                add(id, ver);

                st[ver] = true;
            }
        }

        int root = 0;

        while (st[root]) root++;

        dfs(root);

        cout << min(f[root][0], f[root][1]) << endl;
    }

    return 0;
}

#define ll long long

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N = 1e5 + 11;

int n, m, arr[N]; ll tr[N];

int lowbit(int x) {

    return x & -x;
}

void add(int x, int c) {

    for (int i = x; i <= n; i += lowbit(i)) tr[i] += c;
}

ll sum(int x) {

    ll res = 0;

    for (int i = x; i; i -= lowbit(i)) res += tr[i];

    return res;
}

int main(){

    cin >> n >> m;

    for (int i = 1; i <= n; i++) cin >> arr[i];

    for (int i = 1; i <= n; i++) add(i, arr[i] - arr[i - 1]);

    for (int i = 1; i <= m; i++) {

        char op[2];

        int l, r, d;

        cin >> op >> l;

        if (*op == 'C') {

            cin >> r >> d;

            add(l, d), add(r + 1, -d);
        }
        else cout << sum(l) << endl;

    }

    return 0;
}