*题目描述：
在一个小国家中，一个新的小镇终于建成了！如往常一样，Mirko获得了“首席税务巡查员”的职位。他的任务是保证正确地计算各公司的收入情况。一共有N家办公室坐落在主干道上，从左到右被编号为1~N。一开始，所有办公室一开始都是空的。随后，一些公司会搬入或搬出某些办公室。Mirko时不时地会经过某些办公室并审查在这些办公室中，最富有的公司的账目。
一个公司被以如下的方式描述：
T-表示搬入的第一天。
K-表示搬入的办公室的标号。
Z-公司每日的盈利。（可以是负值表示亏损）
S-公司搬入时的公司财务情况。（即公司的账户资金，也可以是负值）
如果一家公司已经在 K 办公室了，当有新公司要进入 K 办公室时，这家公司会立刻搬出。
新公司第一天并不会运营，盈利从第二天开始计算。
Mirko的审查以 3 个整数来描述：
T-审查的时间。
A 和 B-Mirko会检查 A 办公室至 B 办公室（包括A和B）之间的公司。
Mirko只会在一天结束时检查，所有公司这时已经计算完成了当天利润。
*输入：
第一行包含 2 个正整数：N（1<=N<=100000）表示办公室的数量和M（1<=M<=300000）表示事件的个数。
接下来 M 行，遵循以下格式：“1 T K Z S”或“2 T A B”（含义如题目描述）。其中 T 会严格递增，并且最后一天小于 1000000,Z 和 S 的绝对值也严格小于 1000000。
（注意A可能大于B）
*输出：
对于每次Mirko的审查，每行输出一个整数，表示当天最富有的公司的资产（可以为负）。如果Mirko经过的所有办公室中都没有公司入驻，则输出“nema”（不加引号）。
*题解：
分块。题目的意思大概就是求一个区间的半平面交（相当于bzoj1007的水平可见直线）。然而数据只有10的5次方，可以分块搞。每次修改就暴力重构这个块，在块内做半平面交。查询的话如果在同一块的话就暴力查，否则先把头尾两个不全的块暴力查一边，中间完整的块就按之前维护的半平面交查过去。然后因为t是单调的，所以可以计一个left表示当前这个块内查到了第几条直线上。
*代码：

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#ifdef WIN32

    #define LL "%I64d"

#else

    #define LL "%lld"

#endif

#ifdef CT

    #define debug(...) printf(__VA_ARGS__)

    #define setfile()

#else

    #define debug(...)

    #define filename ""

    #define setfile() freopen(filename".in", "r", stdin); freopen(filename".out", "w", stdout);

#endif

#define R register

#define getc() (S == T && (T = (S = B) + fread(B, 1, 1 << 15, stdin), S == T) ? EOF : *S++)

#define dmax(_a, _b) ((_a) > (_b) ? (_a) : (_b))

#define dmin(_a, _b) ((_a) < (_b) ? (_a) : (_b))

#define cmax(_a, _b) (_a < (_b) ? _a = (_b) : 0)

#define cmin(_a, _b) (_a > (_b) ? _a = (_b) : 0)

char B[1 << 15], *S = B, *T = B;

inline int FastIn()

{

    R char ch; R int cnt = 0; R bool minus = 0;

    while (ch = getc(), (ch < '0' || ch > '9') && ch != '-') ;

    ch == '-' ? minus = 1 : cnt = ch - '0';

    while (ch = getc(), ch >= '0' && ch <= '9') cnt = cnt * 10 + ch - '0';

    return minus ? -cnt : cnt;

}

#define maxn 100010

#define maxsize 3010

#define inf (1ll << 62)

int id[maxn], block, n, m, left[maxsize], right[maxsize], t;

long long ans;

bool in[maxn], build[maxsize];

struct Poi

{

    int k;

    long long b;

    inline bool operator < (const Poi &that) const

    {

        return k < that.k || (k == that.k && b > that.b);

    }

    inline bool operator == (const Poi &that) const

    {

        return k == that.k && b == that.b;

    }

    inline double operator ^ (const Poi &that) const

    {

        return 1.0 * (that.b - b) / (k - that.k);

    }

}a[maxn], b[maxn], st[maxsize][maxsize];

inline void add(R int x)

{

    R int kk = id[x], l = block * kk, r = block * (kk + 1) - 1, cnt = 0;

    build[kk] = 1;

    cmin(r, n);

    for (R int i = l; i <= r; ++i) if (in[i]) b[++cnt] = a[i];

    std::sort(b + 1, b + cnt + 1);

    #define stack st[kk]

    R int top = 0; b[0].k = -inf;

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

        if (b[i].k != b[i - 1].k)

        {

            for ( ; top; )

            {

                if ( (stack[top].k == b[i].k)

                    || (top > 1

                    && ((b[i] ^ stack[top - 1]) <= (stack[top] ^ stack[top - 1]) ) )

                    )

                    top--;

                else break;

            }

            stack[++top] = b[i];

        }

    left[kk] = 1;

    right[kk] = top;

}

inline void voi(R int l, R int r)

{

    for (R int i = l; i <= r; ++i) if (in[i])

        cmax(ans, 1ll * a[i].k * t + a[i].b);

}

inline void query(R int x)

{

    #define q st[x]

    if (!build[x]) return ;

    for (; left[x] < right[x]; ++left[x])

    {

        R double tmp = q[left[x]] ^ q[left[x] + 1];

        if (tmp >= t) break;

    }

    cmax(ans, 1ll * q[left[x]].k * t + q[left[x]].b);

}

int main()

{

//  setfile();

    n = FastIn(), m = FastIn();

    block = sqrt(n) / 3 + 1;

    for (R int i = 1; i <= n; ++i) id[i] = i / block;

    for ( ; m; --m)

    {

        R int opt = FastIn(); t = FastIn();

        if (opt == 1)

        {

            R int k = FastIn(), z = FastIn(), s = FastIn();

            in[k] = 1; a[k] = (Poi) {z, 1ll * s - 1ll * z * t};

            add(k);

        }

        else

        {

            R int l = FastIn(), r = FastIn();

            if (l > r) std::swap(l, r);

            ans = -inf;

            if (id[l] == id[r]) voi(l, r);

            else

            {

                voi(l, (id[l] + 1) * block - 1);

                voi(id[r] * block, r);

                for (R int i = id[l] + 1; i < id[r]; ++i) query(i);

            }

            if (ans == -inf) puts("nema");

            else printf("%lld\n", ans );

        }

    }

    return 0;

}