Knapsack and Queries

You are given a positive integer $MOD$ first. The knapsack is empty at the start.

You perform $Q$ queries. In each query, you first perform either an ADD or a REMOVE operation, and then a FIND operation.

For ADD, you are given positive integers $w$ and $v$. Put a cookie with weight $w$ and value $v$ into the knapsack.

For REMOVE, take out the cookie with the smallest weight from the knapsack and eat it.

After each ADD or REMOVE, perform FIND. You are given positive integers $l$ and $r$. Determine whether you can choose cookies from the knapsack so that $l \leq (X \bmod MOD) \leq r$, where $X$ is the sum of the weights of the chosen cookies. If you cannot, print -1. Otherwise, print the maximum possible sum of the values of the chosen cookies.

The input is given in the following format.

$MOD$ $Q$ $t'_1$ $w'_1$ $v'_1$ $l'_1$ $r'_1$ $t'_2$ $w'_2$ $v'_2$ $l'_2$ $r'_2$ $\ldots$ $t'_Q$ $w'_Q$ $v'_Q$ $l'_Q$ $r'_Q$

The queries are encrypted as described below. Decrypt $t'_i, w'_i, v'_i, l'_i, r'_i$ to get $t_i, w_i, v_i, l_i, r_i$.

You may assume $1 \leq w_i, v_i \leq 10^9$ and $0 \leq l_i \leq r_i \leq MOD-1$. $t_i=1$ is an ADD+FIND query, and $t_i=2$ is a REMOVE+FIND query, in which case $w_i=v_i=0$. Each cookie given by ADD is heavier than any cookie added by a previous ADD. When REMOVE runs, the knapsack is not empty.

The decryption works as follows.

• Create an instance of the class Crypto.
• For each query, call decode in the order $t', w', v', l', r'$. The return values are $t, w, v, l, r$. Then perform the query and call query with the FIND result.

The code for the Crypto class and usage examples are provided for C++11 (or later), Java, D, and C#. The C++ example is below.

#include <cstdint> //uint8_t, uint32_t

class Crypto {
public:
    Crypto() {
        sm = cnt = 0;
        seed();
    }

    int decode(int z) {
        z ^= next();
        z ^= (next() << 8);
        z ^= (next() << 16);
        z ^= (next() << 22);
        return z;
    }

    void query(long long z) {
        const long long B = 425481007;
        const long long MD = 1000000007;
        cnt++;
        sm = ((sm * B % MD + z) % MD + MD) % MD;
        seed();
    }
private:
    long long sm;
    int cnt;

    uint8_t data[256];
    int I, J;

    void swap_data(int i, int j) {
        uint8_t tmp = data[i];
        data[i] = data[j];
        data[j] = tmp;
    }

    void seed() {
        uint8_t key[8];
        for (int i = 0; i < 4; i++) {
            key[i] = (sm >> (i * 8));
        }
        for (int i = 0; i < 4; i++) {
            key[i+4] = (cnt >> (i * 8));
        }

        for (int i = 0; i < 256; i++) {
            data[i] = i;
        }
        I = J = 0;

        int j = 0;
        for (int i = 0; i < 256; i++) {
            j = (j + data[i] + key[i%8]) % 256;
            swap_data(i, j);
        }
    }

    uint8_t next() {
        I = (I+1) % 256;
        J = (J + data[I]) % 256;
        swap_data(I, J);
        return data[(data[I] + data[J]) % 256];
    }
};

The Crypto class takes about 200 to process $Q = 100000$.

The sample main code is below.

#include <cstdio>
#include <cstdlib>
#include <cstdint> //uint8_t, uint32_t

class Crypto {
    ...
};

int main() {
    int MOD, Q;
    scanf("%d %d", &MOD, &Q);
    Crypto c;
    for (int i = 0; i < Q; i++) {
        int t, w, v, l, r;
        scanf("%d %d %d %d %d", &t, &w, &v, &l, &r);
        t = c.decode(t);
        w = c.decode(w);
        v = c.decode(v);
        l = c.decode(l);
        r = c.decode(r);
        if (t == 1) {
            (add candy(w, v))
        } else {
            (delete candy)
        }
        long long ans = (answer for query(l, r));
        c.query(ans);
        printf("%lld\n", ans);
    }
}

For each query, print the result of the FIND operation.

$0 \leq t'_i, w'_i, v'_i, l'_i, r'_i \leq 2^{30} - 1$, $2 \leq MOD \leq 500$, $1 \leq Q \leq 100000$.

The result of decoding Sample 1:

10
7
1 5 10 5 5
2 0 0 0 9
1 7 10 2 4
1 12 11 9 9
2 0 0 1 1
1 22 10 2 3
1 32 100 4 4

The result of decoding Sample 2:

7
20
1 5 44 0 1
1 11 90 0 3
2 0 0 3 4
1 18 68 1 6
1 25 32 2 3
1 31 22 2 3
1 32 26 1 5
1 36 31 3 6
2 0 0 2 5
1 43 10 3 6
2 0 0 5 6
2 0 0 3 4
2 0 0 2 4
2 0 0 1 5
2 0 0 3 5
1 49 48 0 4
2 0 0 1 5
1 50 36 0 6
1 56 48 3 5
1 59 17 3 5