盲盒流水线

题目信息

时间限制: 1s

空间限制: 256M

输入文件: knapsack.in

输出文件: knapsack.out

题目描述

小 C 有一条制造盲盒的流水线，小 C 家出产的盲盒主打一个良心！

新一批盲盒中含有 $n$ 种不同的手办，第 $i$ 种手办的稀有度为 $v_i$，体积为 $w_i$。小 C 需要生产新一批的 $q$ 个盲盒，为了保证盲盒的随机性，第 $i$ 个盲盒只会在第 $[l_i, r_i]$ 种手办中，挑选一些手办装进去。第 $i$ 个盲盒的体积为 $m_i$，且第 $i$ 个盲盒内包含的手办遵循小 C 规定的良心盲盒准则：

1. 每种手办最多只能放一个
2. 盲盒内手办的体积总和不超过 $m_i$
3. 盲盒内含手办的稀有度总和是可能的手办组合中最大的

小 C 想知道，对于新一批 $q$ 个盲盒，给定每个盲盒的体积 $m_i$ ，问每个盲盒是否有遵循良心盲盒准则的手办放置方案，如果有，小 C 还想知道每个盲盒中手办的稀有度总和最大值，以及对于每个盲盒，达到稀有度最大值的方案数是多少。注意，对于每个盲盒，两种方案不同当且仅当至少存在一种手办，在一种方案中购买了，而在另一种方案中没有购买。方案数只需要输出对 998244353 取模后的结果即可，如果没有任何遵循良心盲盒准则的方案，请输出 0 0

输入格式

第一行一个正整数 $n$，表示手办的种类数。

接下来 $n$ 行，第 $i$ 行三个正整数 $v_i, w_i$，表示第 $i$ 种手办的稀有度和体积。

接下来一行一个正整数 $q$，表示这批需要生产的盲盒数量。

接下来 $q$ 行，每行三个正整数 $l_i, r_i, m_i$ 表示第 $i$ 个盲盒可以选用的手办编号区间、以及该盲盒的体积。

输出格式

输出 $q$ 行，第 $i$ 行两个正整数依次表示第 $i$ 个盲盒可能的最大稀有度，以及取模后的达到最大稀有度的方案数。（如果没有遵循良心盲盒准则的方案，则输出一行 0 0。

样例

样例输入 1

5
1 5
8 1
1 6
4 10
10 2
5
2 4 1
1 3 6
1 5 10
2 3 5
2 4 4

样例输出 1

8 1
9 1
19 2
8 1
8 1

数据范围

$1 \leq l_i \leq r_i \leq n \leq 20000,1 \leq q \leq 100000,1 \leq m_i \leq 500, 1 \leq w_i \leq 500,1 \leq v_i \leq 10^6$

• subtask1(15 pts): $n, q, m_i \leq 10$
• subtask2(15 pts): $n, q, m_i \leq 200$
• subtask3(10 pts): $n, q \leq 5000, m_i \leq 200$
• subtask4(20 pts): $m_i \leq 5$
• subtask5(15 pts): $n \leq 10000, q \leq 30000$
• subtask6(25 pts): 无限制