小明特别热爱数学，某一天他的脑海里突然冒出来了一个奇特的想法：他认为如果一个整数的各个数位和是 mm 的倍数，那么这个整数自身一定也是 mm 的倍数。但小程却认为小明的这个猜想肯定有bug，但自己找不到。于是他找了 nn 个正整数。请聪明的你挑出这些正整数当中，本身不是 mm 的倍数，但各个数位和是 mm 的倍数的那些数，并按输入顺序输出。

输入格式
输入的第一行有两个正整数 m,nm,n，题意同题目描述。

之后 nn 行，每行有一个正整数，表示小程找的正整数。

输出格式
输出若干行，表示小程 找的正整数中，本身不是 mm 的倍数，但各个数位和是 mm 的倍数的那些数。按照输入顺序输出。

特别地，如果没有符合题意的正整数，输出 None。

输入数据 1
6 5
12
24
33
165
8
输出数据 1
33
165
输入数据 2
8 2
15
9
输出数据 2
None
输入数据 3
7 5
142
106
7777
1000006
25
输出数据 3
142
106
25
说明/提示
【样例 1 解释】

m=6m=6 小程 找到的 55 个正整数的分析如下：

12是6的倍数，数位之和不是6的倍数，所以不符合要求；

24是6的倍数，数位之和是6的倍数，所以不符合要求；

33不是6的倍数，数位之和是6的倍数，所以符合要求输出；

165不是6的倍数，数位之和是6的倍数，所以符合要求输出；

8不是6的倍数，数位之和不是6的倍数，所以不符合要求；

【样例 2 解释】

m=8m=8 小程 找到的 22 个正整数的分析如下：

15不是8的倍数，数位之和不是8的倍数，所以不符合要求；

9不是8的倍数，数位之和不是8的倍数，所以不符合要求；

由于找到的数都不满足要求，所以输出None

数据范围
对于全部数据，保证 1\le m\le 1001≤m≤100，1\le n\le 10^51≤n≤10 
5
 ，小程 找的正整数不超过 10^910 
9
 。

特别地，前 44 个测试点还保证小程找的正整数数位和都是 mm 的倍数。

在你面前摆放着 1010 块金属，它们的重量分别是 a_1,a_2,...,a_{10}a 
1
​
 ,a 
2
​
 ,...,a 
10
​
 。你的任务是将它们熔化后重新打造成一个金属饰品。注意：你只能按照给定的顺序，从第一块开始，依次熔炼每一块金属。

你需要计算：如何熔炼才能使得最终饰品的重量尽可能接近 100100，输出最接近 100100 的饰品重量。若有多个重量符合要求，则输出较大的那个重量。

输入格式
1010 个整数 a_1,a_2,...,a_{10}a 
1
​
 ,a 
2
​
 ,...,a 
10
​
 ，分别表示每块金属的重量，以空格分隔。

输出格式
一个整数，表示最终饰品的重量。

输入数据 1
10 20 30 40 50 60 70 80 90 100
输出数据 1
100
输入数据 2
1 2 3 90 1 2 2 1 1 2 
输出数据 2
101
样例 11 解释

将前 44 块金属熔炼，饰品的总重量为 10+20+30+40=10010+20+30+40=100，与 100100 的差值为 00。

样例 22 解释

将前 66 块金属熔炼，饰品的总重量为 9999；将前 77 块金属熔炼，饰品的总重量为 101101，两种方案中，饰品的重量距离 100100 的差值均为 11，按照要求应输出 101101。

数据范围
对于所有数据，1≤a_i≤1001≤a 
i
​
 ≤100。

在一个从灾难性事件中恢复的未来世界，有 nn 个新的定居点和 kk 个水源。每个水源只能建立一个定居点，并且一个水源只能为一个定居点提供水。由于资源紧张，为了保证每个定居点都有足够的水源供应，要求距离最近的两个定居点之间的距离尽可能大。

例如，n=4,k=6n=4,k=6，水源的位置为 0,3,4,7,8,90,3,4,7,8,9。此时为下图所示。

\begin{aligned} \underline{\text{\qquad O\quad l\quad l\quad O\quad O\quad l\quad l\quad O\quad O\quad O\qquad}}\\ \text{\qquad 0\quad\ \quad\ \ \quad 3\ \quad 4\quad\quad\quad\quad 7\quad\ 8\quad\ 9\qquad} \end{aligned}
OllOOllOOO
​
 
0   3 47 8 9
​
 
有许多种分配方案，例如：

0,3,4,90,3,4,9：此时最近距离为 11（3,43,4 之间）；
0,3,7,90,3,7,9：此时最近距离为 22。
输入格式
三个整数 n,k,s_1n,k,s 
1
​
 ，其中 s_1s 
1
​
  为第 11 个水源的位置，其他水源 s_i(i\ge2)s 
i
​
 (i≥2) 的位置由下面公式给出：

s_i = s_{i-1} + ((s_{i-1}\times2357+137) \bmod 10)+1s 
i
​
 =s 
i−1
​
 +((s 
i−1
​
 ×2357+137)mod10)+1。

输出格式
一个整数，即定居点之间最近距离的最大值。

样例
输入数据 1
3 5 0
输出数据 1
8
输入数据 2
25 70 99
输出数据 2
12
样例解释
样例 1 中，水源的位置分别为：0,8,12,14,200,8,12,14,20，在 0,12,200,12,20 三个点设置居住点能使得答案最大。

样例 2 中，有 2525 个定居点和 7070 个水源。从第 11 个水源位置 9999 开始，其他水源的位置根据公式计算。通过合理分配水源，使得定居点之间最近的距离达到最大值为 1212。

数据范围
对于30 \%数据: 2\le n\le k\le10^3对于30%数据:2≤n≤k≤10 
3
 。

对于100 \%数据: 2\le n\le k\le10^6,0\le s_1\le100对于100%数据:2≤n≤k≤10 
6
 ,0≤s 
1
​
 ≤100。

在一个小镇上，电力公司想知道最近一次电力补给是在什么时候。最近一次补给的电力是 E1E1 度。不幸的是，公司忘记了准确的补给日期。只知道到第 TT 天时，仍然剩余 E2E2 度的电力。

小镇上有 HH 家家庭，每个家庭在镇上的时候每天消耗恰好 11 度的电力。由于各种原因，各个家庭们在不同的时间回到小镇和离开小镇，回到小镇的当天开始用电。离开小镇后的次日停止用电，每个家庭在来的那天和离开的那天都会用电。因此在不同的两天中可能电力消耗量差距较大。请你写一个程序，判断电力最近一次补给是在什么时候。

注意:每个家庭在来的那天和离开的那天都会用电。第TT天所有的家庭已用过电，并且补给电力的当天还未开始供电。

如果最终的答案有多个可能，请输出最大的（即，最近的）那一个。

输入格式
第 11 行：四个整数 HH，E1E1，E2E2，TT，用空格隔开。

第 22 到 H+1H+1 行：每行是用空格隔开的两个数字，分别表示一个家庭开始和停止用电的时间。

输出格式
一个正整数，即上一次电力补给的时间。

样例
输入数据 1
3 14 4 10
1 9
5 8
8 12
输出数据 1
6
样例解释1
上一次补给了 1414 度的电力，现在剩余 44 度。最近 1010 天里，有 33 家家庭使用了电力。 电力公司在第 66 天收到 1414 度电力，当天消耗 22 度，第 77 天消耗 22 度，第 88 天消耗 33 度，第 99 天消耗 22 度，第 1010 天消耗 11 度，正好还剩 44 度。

输入数据 2
3 18 6 13
2 5
6 9
8 13
输出数据 2
4
样例解释2
​ 上一次补给了1818度的电力，第1313天剩余66度的电力。有33家家庭使用了电力。电力公司在第44天收到1818度电力的补给，当天消耗11度(剩余1717)，第55天消耗11度(剩余1616)，第66天到第77天各消耗11度(剩余1414)，第88天到第99天，每天消耗22度(剩余1010)。第1010天到第1313天，每天消耗11度，第1313天正好剩余66度。

数据范围
50\%50%的数据保证: 1\le E2\le E1\le 10^31≤E2≤E1≤10 
3
 

100\%100%的数据保证: 1\le E2\le E1\le 10^61≤E2≤E1≤10 
6
 ，1\le T\le 2\times 10^31≤T≤2×10 
3
 ，1\le H\le 1001≤H≤100。

给出两个长度为nn的数组c,tc,t和QQ次询问，每次询问给出两个整数S,VS,V，你需要输出满足c_i > t_i + Sc 
i
​
 >t 
i
​
 +S的个数是否大于等于VV。

输入格式
输入的第一行包含 N（1\le N\le 2\cdot 10^5）N（1≤N≤2⋅10 
5
 ） 和 Q（1\le Q\le 2\cdot 10^5）Q（1≤Q≤2⋅10 
5
 ）。

第二行包含 c_1,c_2,c_3\ldots c_Nc 
1
​
 ,c 
2
​
 ,c 
3
​
 …c 
N
​
 （1\le c_i\le 10^61≤c 
i
​
 ≤10 
6
 ）。

第三行包含 t_1,t_2,t_3\ldots t_Nt 
1
​
 ,t 
2
​
 ,t 
3
​
 …t 
N
​
 （1\le t_i\le 10^61≤t 
i
​
 ≤10 
6
 ）。

以下 QQ 行，每行包含两个整数 VV（1\le V\le N1≤V≤N）和 SS（1\le S\le 10^61≤S≤10 
6
 ）。

输出格式
对 QQ 个询问的每一个输出一行，输出 YES（是）或 NO（否）。

输入数据 1
5 5
3 5 7 9 12
4 2 3 3 8
1 5
1 6
3 3
4 2
5 1
输出数据 1
YES
NO
YES
YES
NO
提示
样例解释
对于第一个询问，c_4 > t_4 + Sc 
4
​
 >t 
4
​
 +S

对于第二个询问，没有成立的c_i > t_i + Sc 
i
​
 >t 
i
​
 +S

对于第三个询问，成立的ii为3,4,53,4,5。

测试点性质
测试点 2-42−4：N,Q\le 10^3N,Q≤10 
3
 。
测试点 5-95−9：c_i,t_i\le 20c 
i
​
 ,t 
i
​
 ≤20。
测试点 10-1710−17：没有额外限制。

给出一个长度为NN，只含有字符G,HG,H的字符串xx和一个长度为NN，只含有..的字符串yy。

你需要将yy中的..改成GG或者HH（也可以不改），使得对于xx中的任意字符x_ix 
i
​
 ，存在jj使得x_i = y_jx 
i
​
 =y 
j
​
 且|i - j| \leq k∣i−j∣≤k。

输出最少要更改yy中几个字符，并输出任意一种更改的方案（任何满足上述条件的方案均视为正确）

输入格式
每个测试用例包含 TT 个子测试用例。输入的第一行包含 T(1 \le T \le 10)T(1≤T≤10)。以下是 TT 个子测试用例。

每个子测试用例的第一行包含 N(1 \le N \le 10^5)N(1≤N≤10 
5
 ) 和 K(0 \le K \le N-1)K(0≤K≤N−1)。第二行包含一个长度为 NN 的字符串xx。

输出格式
对于 TT 个子测试用例中的每一个，输出两行。

第一行输出输出最少要更改yy中几个字符，

第二行输出一种方案，合法的方案均可通过。

输入数据 1
6
5 0
GHHGG
5 1
GHHGG
5 2
GHHGG
5 3
GHHGG
5 4
GHHGG
2 1
GH
输出数据 1
5
GHHGG
3
.GH.G
2
..GH.
2
...GH
2
...HG
2
HG
提示
样例 1 解释
注意对于某些子测试用例，存在多种可通过的方案。例如，在第四个子测试用例中，以下是另一个可以通过的答案：

\texttt{.GH..}
.GH..
测试点性质
测试点 2-42−4 满足 N \le 10N≤10。
测试点 5-85−8 满足 N \le 40N≤40。
测试点 9-129−12 满足 N \le 10^5N≤10 
5
 。

给定nn个要求和mm种操作和一个有100100个初始值为00的区间。

第ii个要求为区间[s_i,t_i][s 
i
​
 ,t 
i
​
 ]里面的元素必须都大于等于c_ic 
i
​
 。这些要求的区间不会重合。

第ii种操作，给出区间[a_i,b_i][a 
i
​
 ,b 
i
​
 ]。你可以花费m_im 
i
​
 的成本使得这个区间的所有元素都加上p_ip 
i
​
 。每种操作限一次。

求达成所有要求至少要多少花费。

输入格式
第一行两个整数，分别为 NN 和 MM。

第 22 至 (N+1)(N+1) 行，每行三个整数，分别为 s_is 
i
​
 、t_it 
i
​
  和 c_ic 
i
​
  。

第 (N+2)(N+2) 至 (M+N+1)(M+N+1) 行，每行四个整数， 分别为 a_ia 
i
​
 、b_ib 
i
​
 、p_ip 
i
​
  和 m_im 
i
​
 。

输出格式
一个整数，表示最少花费。

输入数据 1
2 4
1 5 2
7 9 3
2 9 2 3
1 6 2 8
1 2 4 2
6 9 1 5
输出数据 1
10
提示
样例解释 1
进行操作1,3,41,3,4。可以满足所有要求，且是最优解。

数据范围
对于 100\%100% 的数据，1 \le N \le 201≤N≤20， 1 \le M \le 101≤M≤10, 1 \le a_i, b_i, s_i, t_i \le 1001≤a 
i
​
 ,b 
i
​
 ,s 
i
​
 ,t 
i
​
 ≤100, 1 \le c_i, p_i \le 10^61≤c 
i
​
 ,p 
i
​
 ≤10 
6
 ， 1 \le m_i \le 10001≤m 
i
​
 ≤1000。