#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 1e5 + 10;

LL tr[N];
int a[N], n, m;

int lowbit(int x)
{
    return x & -x;
}

void add(int u, int c)
{
    for (int i = u; i <= n; i += lowbit(i)) tr[i] += c;
}

LL getS(int u)
{
    LL ans = 0;
    for (int i = u; i ; i -= lowbit(i)) ans += tr[i];
    return ans;
}

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

    for (int i = 1; i <= n; i ++)
    {
        scanf("%d", &a[i]);
        add(i, a[i] - a[i - 1]);
    }

    while (m -- )
    {
        char op[2];
        int l, r, d;
        scanf("%s", op);
        if (*op == 'C')
        {
            scanf("%d%d%d", &l, &r, &d);
            add(l, d);
            add(r + 1, -d);
        } else
        {
            scanf("%d", &d);
            printf("%lld\n", getS(d));
        }
    }

    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

struct Edge {
    int a, b, w;

    bool operator < (const Edge& e) const {
        return w < e.w;
    }
}edges[10010];

int p[2010];

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    int n, m, ans = 0, cnt = 0;

    cin >> n >> m;

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

    for (int i = 0; i < m; i ++)
    {
        int a, b, c, t;
        cin >> t >> a >> b >> c;
        if (t == 1)
        {
            p[find(a)] = find(b);
            ans += c;
            continue;
        }
        edges[cnt ++] = {a, b, c};
    }

    sort(edges, edges + cnt);

    for (int i = 0; i < cnt; i ++)
    {
        int a = edges[i].a, b = edges[i].b, c = edges[i].w;

        int fa = find(a), fb = find(b);

        if (fa == fb) continue;

        ans += c;
        p[fa] = fb;
    }

    cout << ans << endl;

    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

struct Edge {
    int a, b, w;

    bool operator < (const Edge& e) const {
        return w < e.w;
    }
}edges[8010];

int p[310];

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    int n, m, ans = 0;

    cin >> n >> m;

    for (int i = 0; i < m; i ++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        edges[i] = {a, b, c};
    }

    sort(edges, edges + m);

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

    int res;
    for (int i = 0; i < m; i ++)
    {
        int a = edges[i].a, b = edges[i].b, c = edges[i].w;

        int fa = find(a), fb = find(b);

        if (fa == fb) continue;

        ans = c;
        p[fa] = fb;
    }

    cout << n - 1 << " " << ans << endl;

    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

struct Edge {
    int a, b, w;

    bool operator < (const Edge& e) const {
        return w < e.w;
    }
}edges[210];

int p[110];

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    int n, m, sum = 0;

    cin >> n >> m;

    for (int i = 0; i < m; i ++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        sum += c;
        edges[i] = {a, b, c};
    }

    sort(edges, edges + m);

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

    int res;
    for (int i = 0; i < m; i ++)
    {
        int a = edges[i].a, b = edges[i].b, c = edges[i].w;

        int fa = find(a), fb = find(b);

        if (fa == fb) continue;

        res += c;
        p[fa] = fb;
    }

    cout << sum - res << endl;

    return 0;

}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110, inf = 0x3f3f3f3f;

int n;
int g[N][N];
int d[N];
bool st[N];

int kruskal()
{
    memset(d, inf, sizeof d);
    d[1] = 0;

    int ans = 0;
    while (true)
    {
        int v = -1;
        for (int i = 1; i <= n; i ++)
            if (!st[i] && (v == -1 || d[i] < d[v]))
                v = i;

        if (v == -1) break;
        st[v] = true;
        ans += d[v];

        for (int i = 1; i <= n; i ++)
            d[i] = min(d[i], g[v][i]);
    }

    return ans;
}

int main()
{
    cin >> n;

    memset(g, inf, sizeof g);

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

    cout << kruskal() << endl;

    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 505, inf = 0x3f3f3f3f;

int g[N][N];
int d[N];
int n, m;
bool st[N];

int prim()
{
    d[1] = 0;

    int ans = 0;

    while (true)
    {
        int v = -1;
        for (int i = 1; i <= n; i ++)
            if (!st[i] && (v == -1 || d[v] > d[i]))
                v = i;

        if (v == -1) break;

        if (d[v] == inf) return inf;

        st[v] = true;
        ans += d[v];

        for (int i = 1; i <= n; i ++)
            d[i] = min(d[i], g[v][i]);
    }

    return ans;
}

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

    memset(g, inf, sizeof g);
    memset(d, inf, sizeof d);

    while (m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        g[a][b] = g[b][a] = min(c, g[a][b]);
    }

    int ans = prim();

    if (ans == inf) printf("impossible\n");
    else printf("%d\n", ans);

    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>

using namespace std;

typedef pair<int, int> PII;

const int N = 50010, M = 200010, inf = 0x3f3f3f3f;

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

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

void dijkstra(int u, int d[])
{
    priority_queue<PII, vector<PII>, greater<PII>> heap;

    d[u] = 0;
    heap.push({0, u});

    while (heap.size())
    {
        PII t = heap.top();
        heap.pop();
        int weight = t.first, ix = t.second;

        if (st[ix]) continue;
        st[ix] = true;

        for (int i = h[ix]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (d[j] > w[i] + weight)
            {
                d[j] = w[i] + weight;
                heap.push({d[j], j});
            }
        }
    }
    memset(st, false, sizeof st);
}

int dfs(int u, int from, int dis)
{
    if (u == 6) return dis;

    int ans = inf;
    for (int i = 1; i <= 5; i ++)
        if (!st[i])
        {
            int x = sources[i];
            st[i] = true;
            ans = min(ans, dfs(u + 1, i, dis + dist[from][x]));
            st[i] = false;
        }

    return ans;
}

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

    sources[0] = 1;

    for (int i = 1; i <= 5; i ++) scanf("%d", &sources[i]);

    memset(dist, inf, sizeof dist);
    memset(h, -1, sizeof h);

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

    for (int i = 0; i < 6; i ++) dijkstra(sources[i], dist[i]);

    printf("%d\n", dfs(1, 0, 0));

    return 0;

}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 2010;

double g[N][N];
double d[N];
int n, m, S, T;
bool st[N];

double dijkstra()
{
    d[S] = 1;

    while (true)
    {
        int v = -1;

        for (int i = 1; i <= n; i ++)
            if (!st[i] && (v == -1 || d[i] > d[v]))
                v = i;

        if (v == -1) break;
        st[v] = true;

        for (int i = 1; i <= n; i ++)
            d[i] = max(d[i], d[v] * g[v][i]);
    }

    return d[T];
}

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

    while (m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        double t = (100.0 - c) / 100;
        g[a][b] = g[b][a] = max(g[a][b], t);
    }

    scanf("%d%d", &S, &T);

    printf("%.8lf", 100 / dijkstra());

    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 810, M = 3000, inf = 0x3f3f3f3f;

int h[N], w[M], e[M], ne[M], idx;
int n, p, m, d[N], id[N];
bool st[N];

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

int spfa(int u)
{
    memset(st, false, sizeof st);
    memset(d, inf, sizeof d);

    queue<int> q;
    q.push(u);
    st[u] = true;
    d[u] = 0;

    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 (d[j] > d[t] + w[i])
            {
                d[j] = d[t] + w[i];
                if (!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    int ans = 0;
    for (int i = 0; i < n; i ++)
    {
        int t = id[i];
        if (d[t] == inf) return inf;
        ans += d[t];
    }

    return ans;
}

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

    for (int i = 0; i < n; i ++) scanf("%d", &id[i]);

    memset(h, -1, sizeof h);

    for (int i = 0; i < m; i ++)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c), add(b, a, c);
    }

    int ans = inf;

    for (int i = 1; i <= p; i ++) ans = min(ans, spfa(i));

    printf("%d\n", ans);

    return 0;
}