第十三届蓝桥杯省赛真题 Java 研究生组【原卷】

以你之姓@ 2024-04-06 15:51 82阅读 0赞

#### 文章目录 ####

*  发现宝藏
 *  【考生须知】
 *  试题 A: 排列字母
 *  试题 B: 灭鼠先锋
 *  试题 C: 质因数个数
 *  试题 D: 数位排序
 *  试题 E: 蜂巢
 *  试题  F : \\mathrm\{F\}: F: 爬树的甲壳虫
 *  试题 G: 重新排序
 *  试题  H \\mathrm\{H\} H : 技能升级
 *  试题 I: 最优清零方案
 *  试题  J : \\mathrm\{J\}: J: 推导部分和

## 发现宝藏 ##

前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。【[宝藏入口][Link 1]】。

--------------------

第十三届蓝桥杯大赛软件赛省赛  Java 研究生 组

--------------------

## 【考生须知】 ##

考试开始后, 选手首先下载题目, 并使用考场现场公布的解压密码解压试题。

考试时间为 4 小时。考试期间选手可浏览自己已经提交的答案, 被浏览的答案允许拷贝。时间截止后，将无法继续提交或浏览答案。

对同一题目, 选手可多次提交答案, 以最后一次提交的答案为准。

选手必须通过浏览器方式提交自己的答案。选手在其它位置的作答或其它方式提交的答案无效。

试题包含 “结果填空” 和 “程序设计” 两种题型。

结果填空题: 要求选手根据题目描述直接填写结果。求解方式不限。不要求源代码。把结果填空的答案直接通过网页提交即可, 不要书写多余的内容。

程序设计题: 要求选手设计的程序对于给定的输入能给出正确的输出结果。考生的程序只有能运行出正确结果才有机会得分。

注意: 在评卷时使用的输入数据与试卷中给出的示例数据可能是不同的。选手的程序必须是通用的, 不能只对试卷中给定的数据有效。

所有源码必须在同一文件中。调试通过后，拷贝提交。

注意: 不要使用 package 语句。

注意：选手代码的主类名必须为: Main, 否则会被判为无效代码。

注意: 如果程序中引用了类库, 在提交时必须将 import 语句与程序的其他部分同时提交。只允许使用 Java 自带的类库。

--------------------

## 试题 A: 排列字母 ##

本题总分: 5 分

**【问题描述】**

小蓝要把一个字符串中的字母按其在字母表中的顺序排列。

例如, LANQIAO 排列后为 AAILNOQ。

又如, GOODGOODSTUDYDAYDAYUP 排列后为 AADDDDDGGOOOOPSTUUYYY

请问对于以下字符串, 排列之后字符串是什么?

WHERETHEREISAWILLTHEREISAWAY

**【答案提交】**

这是一道结果填空的题, 你只需要算出结果后提交即可。本题的结果为一个由大写字母组成的字符串, 在提交答案时只填写这个字符串, 填写多余的内容将无法得分。

--------------------

## 试题 B: 灭鼠先锋 ##

本题总分: 5 分

**【问题描述】**

灭鼠先锋是一个老少咸宜的棋盘小游戏, 由两人参与, 轮流操作。

灭鼠先锋的棋盘有各种规格, 本题中游戏在两行四列的棋盘上进行。游戏的规则为: 两人轮流操作, 每次可选择在棋盘的一个空位上放置一个棋子, 或在同一行的连续两个空位上各放置一个棋子, 放下棋子后使棋盘放满的一方输掉游戏。

小蓝和小乔一起玩游戏, 小蓝先手, 小乔后手。小蓝可以放置棋子的方法很多, 通过旋转和翻转可以对应如下四种情况:

![在这里插入图片描述][fc918cef11984fa384f1e1646bb13689.png]

其中 0 表示棋盘上的一个方格为空，  x \\mathrm\{x\} x 表示该方格已经放置了棋子。

请问, 对于以上四种情况, 如果小蓝和小乔都是按照对自己最优的策略来玩游戏, 小蓝是否能获胜。如果获胜, 请用  V \\mathrm\{V\} V 表示, 否则用  L \\mathrm\{L\} L 表示。请将四种情况的胜负结果挍顺序连接在一起提交。

**【答案提交】**

这是一道结果填空的题, 你只需要算出结果后提交即可。本题的结果为一个长度为 4 的由大写字母  V \\mathrm\{V\} V 和  L \\mathrm\{L\} L 组成的字符串, 如 VVLL, 在提交答案时只填写这个字符串, 填写多余的内容将无法得分。

--------------------

## 试题 C: 质因数个数 ##

时间限制:  5.0 s 5.0 \\mathrm\{~s\} 5.0s 内存限制:  512.0 M B 512.0 \\mathrm\{MB\} 512.0MB 本题总分: 10 分

**【问题描述】**

给定正整数  n n n, 请问有多少个质数是  n n n 的约数。

**【输入格式】**

输入的第一行包含一个整数  n n n 。

**【输出格式】**

输出一个整数, 表示  n n n 的质数约数个数。

**【样例输入】**

396 \\begin\{array\}\{llllll\}396\\end\{array\} 396

**【样例输出】**

3 \\begin\{array\}\{llllll\}3\\end\{array\} 3

**【样例说明】**

396 有  2 , 3 , 11 2,3,11 2,3,11 三个质数约数。

**【评测用例规模与约定】**

对于  30 % 30 \\% 30% 的评测用例,  1 ≤ n ≤ 10000 1 \\leq n \\leq 10000 1≤n≤10000 。

对于  60 % 60 \\% 60% 的评测用例,  1 ≤ n ≤ 1 0 9 1 \\leq n \\leq 10^\{9\} 1≤n≤109 。

对于所有评测用例,  1 ≤ n ≤ 1 0 16 1 \\leq n \\leq 10^\{16\} 1≤n≤1016 。

--------------------

## 试题 D: 数位排序 ##

时间限制:  1.0 s 1.0 \\mathrm\{~s\} 1.0s 内存限制:  512.0 M B 512.0 \\mathrm\{MB\} 512.0MB 本题总分： 10 分

**【问题描述】**

小蓝对一个数的数位之和很感兴趣, 今天他要按照数位之和给数排序。当两个数各个数位之和不同时, 将数位和较小的排在前面, 当数位之和相等时,将数值小的排在前面。

例如, 2022 排在 409 前面, 因为 2022 的数位之和是 6 , 小于 409 的数位之和 13 。

又如, 6 排在 2022 前面, 因为它们的数位之和相同, 而 6 小于 2022 。

给定正整数  n , m n, m n,m, 请问对 1 到  n n n 采用这种方法排序时，排在第  m m m 个的元素是多少?

**【输入格式】**

输入第一行包含一个正整数  n n n 。

第二行包含一个正整数  m m m 。

**【输出格式】**

输出一行包含一个整数, 表示答案。

**【样例输入】**

13 \\begin\{array\}\{llllll\}13\\end\{array\} 13

5 \\begin\{array\}\{llllll\}5\\end\{array\} 5

**【样例输出】**

3 \\begin\{array\}\{llllll\}3\\end\{array\} 3

**【样例说明】**

1 到 13 的排序为:  1 , 10 , 2 , 11 , 3 , 12 , 4 , 13 , 5 , 6 , 7 , 8 , 9 1,10,2,11,3,12,4,13,5,6,7,8,9 1,10,2,11,3,12,4,13,5,6,7,8,9 。第 5 个数为 3 。

**【评测用例规模与约定】**

对于  30 % 30 \\% 30% 的评测用例,  1 ≤ m ≤ n ≤ 300 1 \\leq m \\leq n \\leq 300 1≤m≤n≤300 。

对于  50 % 50 \\% 50% 的评测用例，  1 ≤ m ≤ n ≤ 1000 1 \\leq m \\leq n \\leq 1000 1≤m≤n≤1000 。

对于所有评测用例，  1 ≤ m ≤ n ≤ 1 0 6 1 \\leq m \\leq n \\leq 10^\{6\} 1≤m≤n≤106 。

--------------------

## 试题 E: 蜂巢 ##

时间限制:  1.0 s 1.0 \\mathrm\{~s\} 1.0s 内存限制:  512.0 M B 512.0 \\mathrm\{MB\} 512.0MB 本题总分: 15 分

**【问题描述】**

蜂巢由大量的六边形拼接而成, 定义蜂巢中的方向为: 0 表示正西方向, 1 表示西偏北  6 0 ∘ , 2 60^\{\\circ\}, 2 60∘,2 表示东偏北  6 0 ∘ , 3 60^\{\\circ\}, 3 60∘,3 表示正东, 4 表示东偏南  6 0 ∘ , 5 60^\{\\circ\}, 5 60∘,5 表示西偏南  6 0 ∘ 60^\{\\circ\} 60∘ 。

对于给定的一点  O O O, 我们以  O O O 为原点定义坐标系, 如果一个点  A A A 由  O O O 点先向  d d d 方向走  p p p 步再向  ( d + 2 )   m o d   6 (d+2) \\bmod 6 (d\+2)mod6 方向 (  d d d 的顺时针  12 0 ∘ 120^\{\\circ\} 120∘ 方向) 走  q q q 步到达, 则这个点的坐标定义为  ( d , p , q ) (d, p, q) (d,p,q) 。在蜂窝中, 一个点的坐标可能有多种。

下图给出了点  B ( 0 , 5 , 3 ) B(0,5,3) B(0,5,3) 和点  C ( 2 , 3 , 2 ) C(2,3,2) C(2,3,2) 的示意。

![在这里插入图片描述][7b1169e426604971a08e52bf0ac93e50.png]

给定点  ( d 1 , p 1 , q 1 ) \\left(d\_\{1\}, p\_\{1\}, q\_\{1\}\\right) (d1,p1,q1) 和点  ( d 2 , p 2 , q 2 ) \\left(d\_\{2\}, p\_\{2\}, q\_\{2\}\\right) (d2,p2,q2), 请问他们之间最少走多少步可以到达?

**【输入格式】**

输入一行包含 6 个整数  d 1 , p 1 , q 1 , d 2 , p 2 , q 2 d\_\{1\}, p\_\{1\}, q\_\{1\}, d\_\{2\}, p\_\{2\}, q\_\{2\} d1,p1,q1,d2,p2,q2 表示两个点的坐标, 相邻两个整数之间使用一个空格分隔。

**【输出格式】**

输出一行包含一个整数表示两点之间最少走多少步可以到达。

**【样例输入】**

0 5 3 2 3 2 \\begin\{array\}\{llllll\}0 & 5 & 3 & 2 & 3 & 2\\end\{array\} 053232

**【样例输出】**

7 \\begin\{array\}\{llllll\}7\\end\{array\} 7

**【评测用例规模与约定】**

对于  25 % 25 \\% 25% 的评测用例,  p 1 , p 2 ≤ 1 0 3 p\_\{1\}, p\_\{2\} \\leq 10^\{3\} p1,p2≤103;

对于  50 % 50 \\% 50% 的评测用例,  p 1 , p 2 ≤ 1 0 5 p\_\{1\}, p\_\{2\} \\leq 10^\{5\} p1,p2≤105;

对于  75 % 75 \\% 75% 的评测用例,  p 1 , p 2 ≤ 1 0 7 p\_\{1\}, p\_\{2\} \\leq 10^\{7\} p1,p2≤107;

对于所有评测用例,  0 ≤ d 1 , d 2 ≤ 5 , 0 ≤ q 1 < p 1 ≤ 1 0 9 , 0 ≤ q 2 < p 2 ≤ 1 0 9 0 \\leq d\_\{1\}, d\_\{2\} \\leq 5,0 \\leq q\_\{1\}<p\_\{1\} \\leq 10^\{9\}, 0 \\leq q\_\{2\}<p\_\{2\} \\leq 10^\{9\} 0≤d1,d2≤5,0≤q1<p1≤109,0≤q2<p2≤109 。

--------------------

## 试题  F : \\mathrm\{F\}: F: 爬树的甲壳虫 ##

时间限制:  1.0 s 1.0 \\mathrm\{~s\} 1.0s 内存限制:  512.0 M B 512.0 \\mathrm\{MB\} 512.0MB 本题总分: 15 分

**【问题描述】**

有一只甲壳虫想要爬上一颗高度为  n n n 的树, 它一开始位于树根, 高度为 0 ,当它尝试从高度  i − 1 i-1 i−1 爬到高度为  i i i 的位置时有  P i P\_\{i\} Pi 的概率会掉回树根, 求它从树根爬到树顶时，经过的时间的期望值是多少。

**【输入格式】**

输入第一行包含一个整数  n n n 表示树的高度。

接下来  n n n 行每行包含两个整数  x i , y i x\_\{i\}, y\_\{i\} xi,yi, 用一个空格分隔, 表示  P i = x i y i P\_\{i\}=\\frac\{x\_\{i\}\}\{y\_\{i\}\} Pi=yixi 。

**【输出格式】**

输出一行包含一个整数表示答案, 答案是一个有理数, 请输出答案对质数 998244353 取模的结果。其中有理数  a b \\frac\{a\}\{b\} ba 对质数  P P P 取模的结果是整数  c c c 满足  0 ≤ c < P 0 \\leq c<P 0≤c<P 且  c ⋅ b ≡ a (   m o d   P ) c \\cdot b \\equiv a(\\bmod P) c⋅b≡a(modP) 。

**【样例输入 1】**

1 \\begin\{array\}\{llllll\}1\\end\{array\} 1

1 2 \\begin\{array\}\{llllll\}1&2\\end\{array\} 12

**【样例输出 1】**

2 \\begin\{array\}\{llllll\}2\\end\{array\} 2

**【样例输入 2】**

3 \\begin\{array\}\{llllll\}3\\end\{array\} 3

1 2 \\begin\{array\}\{llllll\}1&2\\end\{array\} 12

3 5 \\begin\{array\}\{llllll\}3&5\\end\{array\} 35

7 11 \\begin\{array\}\{llllll\}7&11\\end\{array\} 711

**【样例输出 2】**

623902744 \\begin\{array\}\{llllll\}623902744\\end\{array\} 623902744

**【评测用例规模与约定】**

对于  20 % 20 \\% 20% 的评测用例,  n ≤ 2 , 1 ≤ x i < y i ≤ 20 n \\leq 2,1 \\leq x\_\{i\}<y\_\{i\} \\leq 20 n≤2,1≤xi<yi≤20 ，

对于  50 % 50 \\% 50% 的评测用例,  n ≤ 500 , 1 ≤ x i < y i ≤ 200 n \\leq 500,1 \\leq x\_\{i\}<y\_\{i\} \\leq 200 n≤500,1≤xi<yi≤200 ；

对于所有评测用例,  1 ≤ n ≤ 100000 , 1 ≤ x i < y i ≤ 1 0 9 1 \\leq n \\leq 100000,1 \\leq x\_\{i\}<y\_\{i\} \\leq 10^\{9\} 1≤n≤100000,1≤xi<yi≤109 。

--------------------

## 试题 G: 重新排序 ##

时间限制:  1.0 s 1.0 \\mathrm\{~s\} 1.0s 内存限制:  512.0 M B 512.0 \\mathrm\{MB\} 512.0MB 本题总分: 20 分

**【问题描述】**

给定一个数组  A A A 和一些查询  L i , R i L\_\{i\}, R\_\{i\} Li,Ri, 求数组中第  L i L\_\{i\} Li 至第  R i R\_\{i\} Ri 个元素之和。

小蓝觉得这个问题很无聊, 于是他想重新排列一下数组, 使得最终每个查询结果的和尽可能地大。小蓝想知道相比原数组, 所有查询结果的总和最多可以增加多少?

**【输入格式】**

输入第一行包含一个整数  n n n 。

第二行包含  n n n 个整数  A 1 , A 2 , ⋯   , A n A\_\{1\}, A\_\{2\}, \\cdots, A\_\{n\} A1,A2,⋯,An, 相邻两个整数之间用一个空格分隔。

第三行包含一个整数  m m m 表示查论的数目。

接下来  m m m 行, 每行包含两个整数  L i 、 R i L\_\{i\} 、 R\_\{i\} Li、Ri, 相邻两个整数之间用一个空格分谝。

**【输出格式】**

输出一行包含一个整数表示答案。

**【样例输入】**

5 \\begin\{array\}\{lllll\}5\\end\{array\} 5

1 2 3 4 5 \\begin\{array\}\{lllll\}1 & 2 & 3 & 4 & 5\\end\{array\} 12345

2 \\begin\{array\}\{lllll\}2\\end\{array\} 2

1 3 \\begin\{array\}\{lllll\}1&3\\end\{array\} 13

2 5 \\begin\{array\}\{lllll\}2&5\\end\{array\} 25

**【样例输出】**

4 \\begin\{array\}\{lllll\}4\\end\{array\} 4

**【样例说明】**

原来的和为  6 + 14 = 20 6+14=20 6\+14=20, 重新排列为  ( 1 , 4 , 5 , 2 , 3 ) (1,4,5,2,3) (1,4,5,2,3) 后和为  10 + 14 = 24 10+14=24 10\+14=24, 增加了 4 。

**【评测用例规模与约定】**

对于  30 % 30 \\% 30% 的评测用例,  n , m ≤ 50 n, m \\leq 50 n,m≤50 ；

对于  50 % 50 \\% 50% 的评测用例,  n , m ≤ 500 n, m \\leq 500 n,m≤500 ；

对于  70 % 70 \\% 70% 的评测用例,  n , m ≤ 5000 n, m \\leq 5000 n,m≤5000 ，

对于所有评测用例,  1 ≤ n , m ≤ 1 0 5 , 1 ≤ A i ≤ 1 0 6 , 1 ≤ L i ≤ R i ≤ 1 0 6 1 \\leq n, m \\leq 10^\{5\}, 1 \\leq A\_\{i\} \\leq 10^\{6\}, 1 \\leq L\_\{i\} \\leq R\_\{i\} \\leq 10^\{6\} 1≤n,m≤105,1≤Ai≤106,1≤Li≤Ri≤106 。

--------------------

## 试题  H \\mathrm\{H\} H : 技能升级 ##

时间限制:  1.0 s 1.0 \\mathrm\{~s\} 1.0s 内存限制:  512.0 M B 512.0 \\mathrm\{MB\} 512.0MB 本题总分: 20 分

**【问题描述】**

小蓝最近正在玩一款 RPG 游戏。他的角色一共有  N N N 个可以加攻击力的技能。其中第  i i i 个技能首次升级可以提升  A i A\_\{i\} Ai 点攻击力, 以后每次升级增加的点数都会减少  B i B\_\{i\} Bi 。 ⌈ A i B i ⌉ \\left\\lceil\\frac\{A\_i\}\{B\_i\}\\right\\rceil ⌈BiAi⌉ (上取整) 次之后, 再升级该技能将不会改变攻击力。

现在小蓝可以总计升级  M M M 次技能, 他可以任意选择升级的技能和次数。请你计算小蓝最多可以提高多少点攻击力?

**【输入格式】**

输入第一行包含两个整数  N N N 和  M M M 。

以下  N N N 行每行包含两个整数  A i A\_\{i\} Ai 和  B i B\_\{i\} Bi 。

**【输出格式】**

输出一行包含一个整数表示答案。

**【样例输入】**

3 6 \\begin\{array\}\{lllll\}3&6\\end\{array\} 36

10 5 \\begin\{array\}\{lllll\}10&5\\end\{array\} 105

9 2 \\begin\{array\}\{lllll\}9&2\\end\{array\} 92

8 1 \\begin\{array\}\{lllll\}8&1\\end\{array\} 81

**【样例输出】**

4 7 \\begin\{array\}\{lllll\}4&7\\end\{array\} 47

**【评测用例规模与约定】**

对于  40 % 40 \\% 40% 的评测用例,  1 ≤ N , M ≤ 1000 1 \\leq N, M \\leq 1000 1≤N,M≤1000 ，

对于  60 % 60 \\% 60% 的评测用例,  1 ≤ N ≤ 1 0 4 , 1 ≤ M ≤ 1 0 7 1 \\leq N \\leq 10^\{4\}, 1 \\leq M \\leq 10^\{7\} 1≤N≤104,1≤M≤107 ；

对于所有评测用例,  1 ≤ N ≤ 1 0 5 , 1 ≤ M ≤ 2 × 1 0 9 , 1 ≤ A i , B i ≤ 1 0 6 1 \\leq N \\leq 10^\{5\}, 1 \\leq M \\leq 2 \\times 10^\{9\}, 1 \\leq A\_\{i\}, B\_\{i\} \\leq 10^\{6\} 1≤N≤105,1≤M≤2×109,1≤Ai,Bi≤106 。

--------------------

## 试题 I: 最优清零方案 ##

时间限制:  3.0 s 3.0 \\mathrm\{~s\} 3.0s 内存限制:  512.0 M B 512.0 \\mathrm\{MB\} 512.0MB 本题总分: 25 分

**【问题描述】**

给定一个长度为  N N N 的数列  A 1 , A 2 , ⋯   , A N A\_\{1\}, A\_\{2\}, \\cdots, A\_\{N\} A1,A2,⋯,AN 。现在小蓝想通过若干次操作将这个数列中每个数字清零。

每次操作小蓝可以选择以下两种之一:

1.  选择一个大于 0 的整数, 将它减去 1 :
2.  选择连续  K K K 个大于 0 的整数, 将它们各减去 1 。

小蓝最少经过几次操作可以将整个数列清零?

**【输入格式】**

输入第一行包含两个整数  N N N 和  K K K 。

第二行包含  N N N 个整数  A 1 , A 2 , ⋯   , A N A\_\{1\}, A\_\{2\}, \\cdots, A\_\{N\} A1,A2,⋯,AN 。

**【输出格式】**

输出一个整数表示答案。

**【样例输入】**

4 2 \\begin\{array\}\{lllll\}4&2\\end\{array\} 42

1 2 3 4 \\begin\{array\}\{llll\}1 & 2 & 3 & 4\\end\{array\} 1234

**【样例输出】**

6 \\begin\{array\}\{lllll\}6\\end\{array\} 6

**【评测用例规模与约定】**

对于  20 % 20 \\% 20% 的评测用例，  1 ≤ K ≤ N ≤ 10 1 \\leq K \\leq N \\leq 10 1≤K≤N≤10 。

对于  40 % 40 \\% 40% 的评测用例,  1 ≤ K ≤ N ≤ 100 1 \\leq K \\leq N \\leq 100 1≤K≤N≤100 。

对于  50 % 50 \\% 50% 的评测用例,  1 ≤ K ≤ N ≤ 1000 1 \\leq K \\leq N \\leq 1000 1≤K≤N≤1000 。

对于  60 % 60 \\% 60% 的评测用例,  1 ≤ K ≤ N ≤ 10000 1 \\leq K \\leq N \\leq 10000 1≤K≤N≤10000 。

对于  70 % 70 \\% 70% 的评测用例,  1 ≤ K ≤ N ≤ 100000 1 \\leq K \\leq N \\leq 100000 1≤K≤N≤100000 。

对于所有评测用例,  1 ≤ K ≤ N ≤ 1000000 , 0 ≤ A i ≤ 1000000 1 \\leq K \\leq N \\leq 1000000,0 \\leq A\_\{i\} \\leq 1000000 1≤K≤N≤1000000,0≤Ai≤1000000 。

--------------------

## 试题  J : \\mathrm\{J\}: J: 推导部分和 ##

时间限制:  1.0 s 1.0 \\mathrm\{~s\} 1.0s 内存限制:  512.0 M B 512.0 \\mathrm\{MB\} 512.0MB 本题总分: 25 分

**【问题描述】**

对于一个长度为  N N N 的整数数列  A 1 , A 2 , ⋯ A N A\_\{1\}, A\_\{2\}, \\cdots A\_\{N\} A1,A2,⋯AN, 小蓝想知道下标  l l l 到  r r r 的部分和  ∑ i = l r = A l + A l + 1 + ⋯ + A r \\sum\_\{i=l\}^\{r\}=A\_\{l\}+A\_\{l+1\}+\\cdots+A\_\{r\} ∑i=lr=Al\+Al\+1\+⋯\+Ar 是多少?

然而, 小蓝并不知道数列中每个数的值是多少, 他只知道它的  M M M 个部分和的值。其中第  i i i 个部分和是下标  l i l\_\{i\} li 到  r i r\_\{i\} ri 的部分和  ∑ j = l i r i = A l i + A l i + 1 + ⋯ + A r i \\sum\_\{j=l\_\{i\}\}^\{r\_\{i\}\}=A\_\{l\_\{i\}\}+A\_\{l\_\{i\}+1\}+\\cdots+A\_\{r\_\{i\}\} ∑j=liri=Ali\+Ali\+1\+⋯\+Ari,值是  S i S\_\{i\} Si 。

**【输入格式】**

第一行包含 3 个整数  N 、 M N 、 M N、M 和  Q Q Q 。分别代表数组长度、已知的部分和数量和询问的部分和数量。

接下来  M M M 行, 每行包含 3 个整数  l i , r i , S i l\_\{i\}, r\_\{i\}, S\_\{i\} li,ri,Si 。

接下来  Q Q Q 行, 每行包含 2 个整数  l l l 和  r r r, 代表一个小蓝想知道的部分和。

**【输出格式】**

对于每个询问, 输出一行包含一个整数表示答案。如果答案无法确定, 输出 UNKNOWN。

**【样例输入】**

5 3 3 \\begin\{array\}\{lll\}5 & 3 & 3 \\end\{array\} 533

1 5 15 \\begin\{array\}\{lll\}1 & 5 & 15\\end\{array\} 1515

4 5 9 \\begin\{array\}\{lll\}4 & 5 & 9\\end\{array\} 459

2 3 5 \\begin\{array\}\{lll\}2& 3& 5\\end\{array\} 235

1 5 \\begin\{array\}\{lll\}1& 5 \\end\{array\} 15

1 3 \\begin\{array\}\{lll\}1& 3\\end\{array\} 13

1 2 \\begin\{array\}\{lll\}1&2\\end\{array\} 12

**【样例输出】**

1 5 \\begin\{array\}\{lll\}1& 5\\end\{array\} 15

6 \\begin\{array\}\{lll\}6\\end\{array\} 6

U N K N O W N \\begin\{array\}\{lll\}UNKNOWN\\end\{array\} UNKNOWN

**【评测用例规模与约定】**

对于  10 % 10 \\% 10% 的评测用例,  1 ≤ N , M , Q ≤ 10 , − 100 ≤ S i ≤ 100 1 \\leq N, M, Q \\leq 10,-100 \\leq S\_\{i\} \\leq 100 1≤N,M,Q≤10,−100≤Si≤100 。

对于  20 % 20 \\% 20% 的评测用例,  1 ≤ N , M , Q ≤ 20 , − 1000 ≤ S i ≤ 1000 1 \\leq N, M, Q \\leq 20,-1000 \\leq S\_\{i\} \\leq 1000 1≤N,M,Q≤20,−1000≤Si≤1000 。

对于  30 % 30 \\% 30% 的评测用例,  1 ≤ N , M , Q ≤ 50 , − 10000 ≤ S i ≤ 10000 1 \\leq N, M, Q \\leq 50,-10000 \\leq S\_\{i\} \\leq 10000 1≤N,M,Q≤50,−10000≤Si≤10000 。

对于  40 % 40 \\% 40% 的评测用例,  1 ≤ N , M , Q ≤ 1000 , − 1 0 6 ≤ S i ≤ 1 0 6 1 \\leq N, M, Q \\leq 1000,-10^\{6\} \\leq S\_\{i\} \\leq 10^\{6\} 1≤N,M,Q≤1000,−106≤Si≤106 。

对于  60 % 60 \\% 60% 的评测用例,  1 ≤ N , M , Q ≤ 10000 , − 1 0 9 ≤ S i ≤ 1 0 9 1 \\leq N, M, Q \\leq 10000,-10^\{9\} \\leq S\_\{i\} \\leq 10^\{9\} 1≤N,M,Q≤10000,−109≤Si≤109 。

对于所有评测用例,  1 ≤ N , M , Q ≤ 1 0 5 , − 1 0 12 ≤ S i ≤ 1 0 12 , 1 ≤ l i ≤ r i ≤ N 1 \\leq N, M, Q \\leq 10^\{5\},-10^\{12\} \\leq S\_\{i\} \\leq 10^\{12\}, 1 \\leq l\_\{i\} \\leq r\_\{i\} \\leq N 1≤N,M,Q≤105,−1012≤Si≤1012,1≤li≤ri≤N,

1 ≤ l ≤ r ≤ N 1 \\leq l \\leq r \\leq N 1≤l≤r≤N 。数据保证没有矛盾。

[Link 1]: https://www.captainbed.cn/dl
[fc918cef11984fa384f1e1646bb13689.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/a965f788a6b04a72b4d32e6466c5bd7b.png
[7b1169e426604971a08e52bf0ac93e50.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/8f2363e47cbe4364b812c7a1de7cc02a.png