#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
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];
}
};
int mod;
// 500*100000*8 -> 381MB
struct dp_stack {
long long dp[100001][500];
int w[100000];
int v[100000];
int sp;
};
dp_stack dp0, dp1;
void to(long long *x, long long y) {
if (*x < y) *x = y;
}
int add(int x, int y) {
x += y;
if (x >= mod) x -= mod;
return x;
}
void push(dp_stack *dp, int w, int v) {
for (int i = 0; i < mod; i++) {
dp->dp[dp->sp + 1][i] = dp->dp[dp->sp][i];
}
w %= mod;
for (int i = 0; i < mod; i++) {
to(&dp->dp[dp->sp + 1][add(i, w)], dp->dp[dp->sp][i] + v);
}
dp->w[dp->sp] = w;
dp->v[dp->sp] = v;
dp->sp++;
}
int peek_w(dp_stack *dp) {
return dp->w[dp->sp - 1];
}
int peek_v(dp_stack *dp) {
return dp->v[dp->sp - 1];
}
void pop(dp_stack *dp) {
dp->sp--;
}
int get_size(dp_stack *dp) {
return dp->sp;
}
long long merge(long long *L, long long *R, int l, int r) {
static int qpos[500];
static long long qval[500];
int ql = mod;
int qr = mod;
int k = mod + r;
long long ans = -1;
for (int i = 0; i < mod; i++) {
while (k > mod + l - i) {
k--;
while (ql < qr && qval[ql] <= R[k % mod]) ql++;
qpos[ql - 1] = k;
qval[ql - 1] = R[k % mod];
ql--;
}
while (ql < qr && qpos[qr - 1] >= mod + r - i) qr--;
if (ql < qr) {
to(&ans, L[i] + qval[qr - 1]);
}
}
return ans;
}
int main() {
int q;
scanf("%d\n%d", &mod, &q);
Crypto c;
for (int i = 1; i < mod; i++) {
dp0.dp[0][i] = -1e18;
dp1.dp[0][i] = -1e18;
}
while (q--) {
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) {
push(&dp0, w, v);
} else {
if (get_size(&dp1) == 0) {
while (get_size(&dp0) > 0) {
push(&dp1, peek_w(&dp0), peek_v(&dp0));
pop(&dp0);
}
}
pop(&dp1);
}
long long ans = merge(dp0.dp[dp0.sp], dp1.dp[dp1.sp], l, r + 1);
c.query(ans);
printf("%lld\n", ans);
}
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdGRsaWIuaD4KI2luY2x1ZGUgPHN0ZGludC5oPgoKY2xhc3MgQ3J5cHRvIHsKcHVibGljOiAgICAKICAgIENyeXB0bygpIHsKICAgICAgICBzbSA9IGNudCA9IDA7CiAgICAgICAgc2VlZCgpOwogICAgfQoKICAgIGludCBkZWNvZGUoaW50IHopIHsKICAgICAgICB6IF49IG5leHQoKTsKICAgICAgICB6IF49IChuZXh0KCkgPDwgOCk7CiAgICAgICAgeiBePSAobmV4dCgpIDw8IDE2KTsKICAgICAgICB6IF49IChuZXh0KCkgPDwgMjIpOwogICAgICAgIHJldHVybiB6OwogICAgfQoKICAgIHZvaWQgcXVlcnkobG9uZyBsb25nIHopIHsKICAgICAgICBjb25zdCBsb25nIGxvbmcgQiA9IDQyNTQ4MTAwNzsKICAgICAgICBjb25zdCBsb25nIGxvbmcgTUQgPSAxMDAwMDAwMDA3OwogICAgICAgIGNudCsrOwogICAgICAgIHNtID0gKChzbSAqIEIgJSBNRCArIHopICUgTUQgKyBNRCkgJSBNRDsKICAgICAgICBzZWVkKCk7CiAgICB9CnByaXZhdGU6IAogICAgbG9uZyBsb25nIHNtOwogICAgaW50IGNudDsKCiAgICB1aW50OF90IGRhdGFbMjU2XTsKICAgIGludCBJLCBKOwoKICAgIHZvaWQgc3dhcF9kYXRhKGludCBpLCBpbnQgaikgewogICAgICAgIHVpbnQ4X3QgdG1wID0gZGF0YVtpXTsKICAgICAgICBkYXRhW2ldID0gZGF0YVtqXTsKICAgICAgICBkYXRhW2pdID0gdG1wOyAgICAKICAgIH0KCiAgICB2b2lkIHNlZWQoKSB7CiAgICAgICAgdWludDhfdCBrZXlbOF07CiAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCA0OyBpKyspIHsKICAgICAgICAgICAga2V5W2ldID0gKHNtID4+IChpICogOCkpOwogICAgICAgIH0KICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IDQ7IGkrKykgewogICAgICAgICAgICBrZXlbaSs0XSA9IChjbnQgPj4gKGkgKiA4KSk7CiAgICAgICAgfQoKICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IDI1NjsgaSsrKSB7CiAgICAgICAgICAgIGRhdGFbaV0gPSBpOwogICAgICAgIH0KICAgICAgICBJID0gSiA9IDA7CgogICAgICAgIGludCBqID0gMDsKICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IDI1NjsgaSsrKSB7CiAgICAgICAgICAgIGogPSAoaiArIGRhdGFbaV0gKyBrZXlbaSU4XSkgJSAyNTY7CiAgICAgICAgICAgIHN3YXBfZGF0YShpLCBqKTsKICAgICAgICB9CiAgICB9CgogICAgdWludDhfdCBuZXh0KCkgewogICAgICAgIEkgPSAoSSsxKSAlIDI1NjsKICAgICAgICBKID0gKEogKyBkYXRhW0ldKSAlIDI1NjsKICAgICAgICBzd2FwX2RhdGEoSSwgSik7CiAgICAgICAgcmV0dXJuIGRhdGFbKGRhdGFbSV0gKyBkYXRhW0pdKSAlIDI1Nl07CiAgICB9Cn07CgppbnQgbW9kOwoKLy8gNTAwKjEwMDAwMCo4IC0+IDM4MU1CCnN0cnVjdCBkcF9zdGFjayB7CiAgbG9uZyBsb25nIGRwWzEwMDAwMV1bNTAwXTsKICBpbnQgd1sxMDAwMDBdOwogIGludCB2WzEwMDAwMF07CiAgaW50IHNwOwp9OwpkcF9zdGFjayBkcDAsIGRwMTsKCnZvaWQgdG8obG9uZyBsb25nICp4LCBsb25nIGxvbmcgeSkgewogIGlmICgqeCA8IHkpICp4ID0geTsKfQoKaW50IGFkZChpbnQgeCwgaW50IHkpIHsKICB4ICs9IHk7CiAgaWYgKHggPj0gbW9kKSB4IC09IG1vZDsKICByZXR1cm4geDsKfQoKdm9pZCBwdXNoKGRwX3N0YWNrICpkcCwgaW50IHcsIGludCB2KSB7CiAgZm9yIChpbnQgaSA9IDA7IGkgPCBtb2Q7IGkrKykgewogICAgZHAtPmRwW2RwLT5zcCArIDFdW2ldID0gZHAtPmRwW2RwLT5zcF1baV07CiAgfQogIHcgJT0gbW9kOwogIGZvciAoaW50IGkgPSAwOyBpIDwgbW9kOyBpKyspIHsKICAgIHRvKCZkcC0+ZHBbZHAtPnNwICsgMV1bYWRkKGksIHcpXSwgZHAtPmRwW2RwLT5zcF1baV0gKyB2KTsKICB9CiAgZHAtPndbZHAtPnNwXSA9IHc7CiAgZHAtPnZbZHAtPnNwXSA9IHY7CiAgZHAtPnNwKys7Cn0KCmludCBwZWVrX3coZHBfc3RhY2sgKmRwKSB7CiAgcmV0dXJuIGRwLT53W2RwLT5zcCAtIDFdOwp9CgppbnQgcGVla192KGRwX3N0YWNrICpkcCkgewogIHJldHVybiBkcC0+dltkcC0+c3AgLSAxXTsKfQoKdm9pZCBwb3AoZHBfc3RhY2sgKmRwKSB7CiAgZHAtPnNwLS07Cn0KCmludCBnZXRfc2l6ZShkcF9zdGFjayAqZHApIHsKICByZXR1cm4gZHAtPnNwOwp9Cgpsb25nIGxvbmcgbWVyZ2UobG9uZyBsb25nICpMLCBsb25nIGxvbmcgKlIsIGludCBsLCBpbnQgcikgewogIHN0YXRpYyBpbnQgcXBvc1s1MDBdOwogIHN0YXRpYyBsb25nIGxvbmcgcXZhbFs1MDBdOwogIGludCBxbCA9IG1vZDsKICBpbnQgcXIgPSBtb2Q7CiAgaW50IGsgPSBtb2QgKyByOwogIGxvbmcgbG9uZyBhbnMgPSAtMTsKICBmb3IgKGludCBpID0gMDsgaSA8IG1vZDsgaSsrKSB7CiAgICB3aGlsZSAoayA+IG1vZCArIGwgLSBpKSB7CiAgICAgIGstLTsKICAgICAgd2hpbGUgKHFsIDwgcXIgJiYgcXZhbFtxbF0gPD0gUltrICUgbW9kXSkgcWwrKzsKICAgICAgcXBvc1txbCAtIDFdID0gazsKICAgICAgcXZhbFtxbCAtIDFdID0gUltrICUgbW9kXTsKICAgICAgcWwtLTsKICAgIH0KICAgIHdoaWxlIChxbCA8IHFyICYmIHFwb3NbcXIgLSAxXSA+PSBtb2QgKyByIC0gaSkgcXItLTsKICAgIGlmIChxbCA8IHFyKSB7CiAgICAgIHRvKCZhbnMsIExbaV0gKyBxdmFsW3FyIC0gMV0pOwogICAgfQogIH0KICByZXR1cm4gYW5zOwp9CgppbnQgbWFpbigpIHsKICBpbnQgcTsKICBzY2FuZigiJWRcbiVkIiwgJm1vZCwgJnEpOwogIENyeXB0byBjOwogIGZvciAoaW50IGkgPSAxOyBpIDwgbW9kOyBpKyspIHsKICAgIGRwMC5kcFswXVtpXSA9IC0xZTE4OwogICAgZHAxLmRwWzBdW2ldID0gLTFlMTg7CiAgfQogIHdoaWxlIChxLS0pIHsKICAgIGludCB0LCB3LCB2LCBsLCByOwogICAgc2NhbmYoIiVkICVkICVkICVkICVkIiwgJnQsICZ3LCAmdiwgJmwsICZyKTsKICAgIHQgPSBjLmRlY29kZSh0KTsKICAgIHcgPSBjLmRlY29kZSh3KTsKICAgIHYgPSBjLmRlY29kZSh2KTsKICAgIGwgPSBjLmRlY29kZShsKTsKICAgIHIgPSBjLmRlY29kZShyKTsKICAgIGlmICh0ID09IDEpIHsKICAgICAgcHVzaCgmZHAwLCB3LCB2KTsKICAgIH0gZWxzZSB7CiAgICAgIGlmIChnZXRfc2l6ZSgmZHAxKSA9PSAwKSB7CiAgICAgICAgd2hpbGUgKGdldF9zaXplKCZkcDApID4gMCkgewogICAgICAgICAgcHVzaCgmZHAxLCBwZWVrX3coJmRwMCksIHBlZWtfdigmZHAwKSk7CiAgICAgICAgICBwb3AoJmRwMCk7CiAgICAgICAgfQogICAgICB9CiAgICAgIHBvcCgmZHAxKTsKICAgIH0KICAgIGxvbmcgbG9uZyBhbnMgPSBtZXJnZShkcDAuZHBbZHAwLnNwXSwgZHAxLmRwW2RwMS5zcF0sIGwsIHIgKyAxKTsKICAgIGMucXVlcnkoYW5zKTsKICAgIHByaW50ZigiJWxsZFxuIiwgYW5zKTsKICB9Cn0K