No further hesitation on those unanswered questions

So now I'll make a dream unchained

题目描述

有 $n$ 个集合 $S_1,S_2,\cdots,S_n$，一开始每个集合都是空的。有 $m$ 个函数 $f_i(x)=k_ix+b_i$，其中 $i=1,2,\cdots m$。

有 $q$ 个时刻，编号分别为 $1\cdots q$，每个时刻开始前都会进行一次操作或查询，然后进行到下一个时刻：

• 1 l r i：给编号在 $[l,r]$ 内的集合都插入一个函数 $f_i(x)$。这里的集合是不可重集，也就是说如果一个函数被插入了两次你应该认为这个集合里只有一个这个函数。
• 2 l r i：对于编号在 $[l,r]$ 内的集合都删除函数 $f_i(x)$。如果这个集合内不存在 $f_i(x)$ 就不操作。
• 3 s l r x：设当前时刻为 $t$，你需要从 $[s,t]$ 中选一个时刻 $p$，从编号在 $[l,r]$ 内的集合中选一个集合 $S_i$，再从 $p$ 时刻的集合 $S_i$ 中选一个函数 $f_j$，你需要最大化 $f_j(x)$ 的值。特别地，若这些集合均为空，你只需输出一行一个字符串 -inf。

输入格式

第一行三个正整数 $n,m,q$。

接下来 $m$ 行，第 $i+1$ 行两个整数 $k_i,b_i$，表示第 $i$ 个函数 $f_i(x)=k_ix+b_i$。

接下来 $q$ 行，每行一个操作。

输出格式

对于每个查询操作输出答案。

样例 $1$ 输入

7 5 14
-2 11
3 6
-3 6
2 8
2 4
1 1 5 2
3 2 4 4 1
3 2 6 7 7
1 2 6 3
2 3 6 2
3 2 5 5 3
2 5 6 1
1 4 7 1
1 4 5 4
3 6 4 5 2
3 7 1 6 5
3 8 2 4 -3
3 8 3 4 4
3 2 3 6 0

样例 $1$ 输出

9
-inf
15
12
21
17
16
11

样例 $1$ 解释

一共有 $10$ 个时刻，以下为 $10$ 个时刻中各个集合的具体情况：

• $\{2\},\{2\},\{2\},\{2\},\{2\},\{\},\{\}$
• $\{2\},\{2\},\{2\},\{2\},\{2\},\{\},\{\}$
• $\{2\},\{2\},\{2\},\{2\},\{2\},\{\},\{\}$
• $\{2\},\{2,3\},\{2,3\},\{2,3\},\{2,3\},\{3\},\{\}$
• $\{2\},\{2,3\},\{3\},\{3\},\{3\},\{3\},\{\}$
• $\{2\},\{2,3\},\{3\},\{3\},\{3\},\{3\},\{\}$
• $\{2\},\{2,3\},\{3\},\{3\},\{3\},\{3\},\{\}$
• $\{2\},\{2,3\},\{3\},\{1,3\},\{1,3\},\{1,3\},\{1\}$
• $\{2\},\{2,3\},\{3\},\{1,3,4\},\{1,3,4\},\{1,3\},\{1\}$
• 再往后的操作均为询问，故不改变集合的具体情况。

对于每次询问，选取的最优 $f_j(x)$ 分别为：

• $f_2(1)=3\times 1+6=9$
• 所有集合均为空，因此输出 -inf
• $f_2(3)=3\times 3+6=15$
• $f_4(4)=2\times 2+8=12$
• $f_2(5)=3\times 5+6=21$
• $f_1(-3)=(-2)\times (-3)+11=17$
• $f_4(4)=2\times 4+8=16$
• $f_1(0)=(-2)\times 0+11=11$

测试点约束

对于 $100\%$ 的数据，$1\le n,m,q\le 10^5,-10^9\le k,b,x\le 10^9$，询问中的 $s$ 不超过当前时刻。

• 特殊性质：对于所有询问，$s$ 均等于当前时刻。