ABC 437

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll A, B;
    cin >> A >> B;
    cout << A * 12 + B << endl;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll H, W, N;
    cin >> H >> W >> N;
    vvll grid(H, vll(W));
    rep(i, H) rep(j, W) {
        cin >> grid[i][j];
    }

    ll ans = 0;

    set<ll> B;
    rep(i, N) {
        ll x;
        cin >> x;
        B.insert(x);
    }
    rep(_, N) {
        rep(i, H) {
            ll tmp = 0;
            rep(j, W) {
                if (B.count(grid[i][j])) tmp++;
            }
            chmax(ans, tmp);
        }
    }
    cout << ans << endl;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    auto cal = []() -> void {
        ll N;
        cin >> N;

        vll W(N), P(N);
        rep(i, N) cin >> W[i] >> P[i];

        ll psum = accumulate(all(P), 0ll);
        vll sums;
        rep(i, N) sums.push_back(W[i] + P[i]);
        sort(all(sums));

        ll ans = 0;
        ll sum = 0;
        for (auto x : sums) {
            if (psum >= sum + x) {
                sum += x;
                ans++;
            }
        }
        cout << ans << endl;
    };

    int t;
    cin >> t;
    rep(i, t) cal();
}

template <typename T>
struct Cumsum {
    vector<T> data;

    Cumsum(vector<T> v) {
        int n = v.size();
        data.resize(n + 1);

        data[0] = 1;
        rep(i, n) {
            data[i + 1] = data[i] + v[i];
        }
    }

    // sum of range [l,r)
    ll sum(int l, int r) {
        return data[r] - data[l];
    }
};

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N, M;
    cin >> N >> M;
    vll A(N), B(M);
    rep(i, N) cin >> A[i];
    rep(i, M) cin >> B[i];
    sort(all(A));
    sort(all(B));

    mint ans = 0;
    Cumsum cumsuma(A), cumsumb(B);
    for (ll b : B) {
        auto it = lower_bound(all(A), b);
        ll d = it - A.begin();
        ans += cumsuma.sum(d, N) - b * (A.end() - it);
        ans += b * d - cumsuma.sum(0, d);
    }
    cout << ans.val() << endl;
}

struct Node {
    vll ids;
    map<ll, Node*> next_node;
};

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N;
    cin >> N;
    vector<Node*> nodes(N + 1, new Node());

    rep(i, N) {
        int id = i + 1;
        ll x, y;
        cin >> x >> y;
        Node* node = nodes[x];
        auto& next_node = node->next_node;
        if (next_node.count(y)) {
            next_node[y]->ids.push_back(id);
        } else {
            // Node tmp_node; という定義方法だとスコープを抜けた段階でデータが捨てられてしまうのでヒープ領域に確保する必要がある
            Node* tmp_node = new Node();
            tmp_node->ids.push_back(id);
            next_node[y] = tmp_node;
        }
        nodes[id] = next_node[y];
    }

    vll ans;
    auto dfs = [&](auto dfs, Node* now) -> void {
        for (auto x : now->ids) ans.push_back(x);
        for (auto [k, v] : now->next_node) dfs(dfs, v);
    };
    dfs(dfs, nodes[0]);

    print(ans);
}

struct Trie {
    vector<map<int, int>> to;
    vint node_id;  // node_id[i]: 数列 i の末端の node id
    vvint ids;     // ids[i]: node_id i を末端とする数列の id

    Trie() {
        to.resize(1);
        ids.resize(1);
        node_id.resize(1, 0);
    }

    void add(int x, int y, int id) {
        int xnode = node_id[x];
        if (!to[xnode].count(y)) {
            int n = to.size();
            to[xnode][y] = n;
            to.push_back(map<int, int>());
            ids.push_back(vint({id}));
            node_id.push_back(n);
            return;
        }

        auto& nid = to[xnode][y];
        node_id.push_back(nid);
        ids[nid].push_back(id);
    }

    void collect(int now, vint& ans) {
        for (int x : ids[now]) ans.push_back(x);
        for (auto [_, v] : to[now]) {
            collect(v, ans);
        }
    }
};

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    Trie trie;

    int N;
    cin >> N;
    rep(i, N) {
        int x, y;
        cin >> x >> y;
        trie.add(x, y, i + 1);
    }

    vint ans;
    trie.collect(0, ans);
    print(ans);
}

struct S {
    ll mx, mi;
};

S op(S a, S b) {
    return {max(a.mx, b.mx), min(a.mi, b.mi)};
}

S e() {
    return {-INF, INF};
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N, Q;
    cin >> N >> Q;
    vll X(N), Y(N);
    rep(i, N) cin >> X[i] >> Y[i];

    segtree<S, op, e> xpy(N), xmy(N);
    rep(i, N) {
        xpy.set(i, {X[i] + Y[i], X[i] + Y[i]});
        xmy.set(i, {X[i] - Y[i], X[i] - Y[i]});
    }

    while (Q--) {
        int t;
        cin >> t;
        if (t == 1) {
            ll i, x, y;
            cin >> i >> x >> y;
            i--;

            ll xx = x + y, yy = x - y;
            xpy.set(i, {xx, xx});
            xmy.set(i, {yy, yy});
        } else {
            ll l, r, x, y;
            cin >> l >> r >> x >> y;
            l--;

            ll xx = x + y, yy = x - y;

            ll ans = 0;

            auto p = xpy.prod(l, r);
            auto m = xmy.prod(l, r);
            chmax(ans, p.mx - xx);
            chmax(ans, -p.mi + xx);
            chmax(ans, m.mx - yy);
            chmax(ans, -m.mi + yy);

            cout << ans << endl;
        }
    }
}