Codeforces Round 927 (Div. 3)

A. Thorns and Coins

Problem - A - Codeforces

During your journey through computer universes, you stumbled upon a very interesting world. It is a path with $n$ consecutive cells, each of which can either be empty, contain thorns, or a coin. In one move, you can move one or two cells along the path, provided that the destination cell does not contain thorns (and belongs to the path). If you move to the cell with a coin, you pick it up.

Here, green arrows correspond to legal moves, and the red arrow corresponds to an illegal move.

You want to collect as many coins as possible. Find the maximum number of coins you can collect in the discovered world if you start in the leftmost cell of the path.

Input

The first line of input contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases. Then the descriptions of the test cases follow.

The first line of each test case contains a single integer $n$ ($1 \le n \le 50$) — the length of the path.

The second line of each test case contains a string of $n$ characters, the description of the path. The character ‘.’ denotes an empty cell, ‘@’ denotes a cell with a coin, and ‘*‘ denotes a cell with thorns. It is guaranteed that the first cell is empty.

Output

For each test case, output a single integer, the maximum number of coins you can collect.

Example

input

3
10
.@@*@.**@@
5
.@@@@
15
.@@..@***..@@@*

output

3
4
3

Note

The picture for the first example is in the problem statement.

Here is the picture for the second example:

And here is the picture for the third example:

翻译

在穿越计算机宇宙的过程中，你偶然发现了一个非常有趣的世界。这是一条有 $n$ 个连续单元格的路径，每个单元格可以是空的、包含荆棘的或一枚硬币。在一次移动中，你可以沿着路径移动一个或两个单元格，前提是目标单元格不包含荆棘(并且属于该路径)。如果你移动到有硬币的单元格，你就把它捡起来。

这里，绿色箭头对应合法移动，红色箭头对应非法移动。

你想收集尽可能多的硬币。如果你从路径最左边的单元格开始，找出你在发现的世界中可以收集的最大硬币数量。

输入

输入的第一行包含一个整数 $t$ ( $1 \le t \le 1000$ ) — 测试用例的数量。然后是测试用例的描述。

每个测试用例的第一行包含一个整数 $n$ ( $1 \le n \le 50$ ) — 路径的长度。

每个测试用例的第二行包含一个 $n$ 个字符的字符串，即路径的描述。字符“。”表示空单元格，“@”表示有硬币的单元格，“*”表示有刺的单元格。保证第一个单元格是空的。

输出

对于每个测试用例，输出一个整数，即您可以收集的最大硬币数量。

Example

input

3
10
.@@*@.**@@
5
.@@@@
15
.@@..@***..@@@*

output

3
4
3

注意

第一个示例的图片在问题陈述中。

这是第二个示例的图片：

这是第三个示例的图片：

代码

#include <iostream>
#include <cstring>
#include <algorithm>
 
using namespace std;
 
int main()
{
	int t;
	cin >> t;
	while (t--){
		int total = 0;
		int n;
		cin >> n;
		string s;
		cin >> s;
		for (int i = 0;i < n;i ++) {
			if (s[i] == s[i + 1] && s[i] == '*') break;
			else if (s[i] == '@') ++total;
		}
		cout << total << '\n';
	}
	return 0;
}

B. Chaya Calendar

Problem - B - Codeforces

The Chaya tribe believes that there are $n$ signs of the apocalypse. Over time, it has been found out that the $i$-th sign occurs every $a_i$ years (in years $a_i$, $2 \cdot a_i$, $3 \cdot a_i$, $\dots$).

According to the legends, for the apocalypse to happen, the signs must occur sequentially. That is, first they wait for the first sign to occur, then strictly after it, the second sign will occur, and so on. That is, if the $i$-th sign occurred in the year $x$, the tribe starts waiting for the occurrence of the $(i+1)$-th sign, starting from the year $x+1$.

In which year will the $n$-th sign occur and the apocalypse will happen?

Input

The first line of the input contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases. Then follow the descriptions of the test cases.

The first line of each test case contains a single integer $n$ ($1 \le n \le 100$) — the number of signs.

The second line of each test case contains $n$ integers $a_1, a_2, a_3, \dots, a_n$ ($1 \le a_i \le 10^6$) — the periodicities of the signs.

Output

For each test case, output a single integer — the year in which all $n$ signs will occur.

Example

input

4
6
3 2 4 5 9 18
5
1 2 3 4 5
5
1 1 1 1 1
6
50 30 711 200 503 1006

output

36
5
5
2012

Note

In the first set of input data of the example:

• The tribe will wait for the first sign in the $3$-rd year;
• the tribe will wait for the second sign in the $4$-th year (since year $2$ have already passed);
• the tribe will wait for the third sign in the $8$-th year (since the second sign has already occurred in the $4$-th year);
• the tribe will wait for the fourth sign in the $10$-th year (since year $5$ have already passed);
• the tribe will wait for the fifth sign in the $18$-th year (since year $9$ have already passed);
• the tribe will wait for the sixth sign in the $36$-th year (since the fifth sign has already occurred in the $18$-th year).

翻译

Chaya 部落相信世界末日有 $n$ 个迹象。随着时间的推移，人们发现，第 $i$ 个迹象每 $a_i$ 年出现一次（年份 $a_i$ 、 $2 \cdot a_i$ 、 $3 \cdot a_i$ 、 $\dots$ ）。

根据传说，世界末日要发生，迹象必须按顺序出现。也就是说，他们首先等待第一个迹象出现，然后紧接着第二个迹象出现，依此类推。也就是说，如果第 $i$ 个迹象出现在年份 $x$ ，部落将从年份 $x+1$ 开始等待第 $(i+1)$ 个迹象的出现。

第 $n$ 个迹象会出现在哪一年，世界末日将会来临？

输入

输入的第一行包含一个整数 $t$ ( $1 \le t \le 1000$ ) — 测试用例的数量。然后是测试用例的描述。

每个测试用例的第一行包含一个整数 $n$ ( $1 \le n \le 100$ ) — 符号的数量。

每个测试用例的第二行包含 $n$ 个整数 $a _ 1, a _ 2, a _ 3, \dots, a _ n$ ( $1 \le a _ i \le 10^6$ ) — 符号的周期性。

输出

对于每个测试用例，输出一个整数——所有 $n$ 符号出现的年份。

Example

input

4
6
3 2 4 5 9 18
5
1 2 3 4 5
5
1 1 1 1 1
6
50 30 711 200 503 1006

output

36
5
5
2012

注意

在示例的第一组输入数据中：

• 部落将等待第 $3$ -年的第一个迹象；
• 部落将等待第 $4$ -年的第二个迹象（因为第 $2$ 年已经过去）；
• 部落将等待第 $8$ -年的第三个迹象（因为第 $4$ -年第二个迹象已经发生）；
• 部落将等待第 $10$ -年的第四个迹象（因为第 $5$ 年已经过去）；
• 部落将等待第 $18$ -年的第五个迹象（因为第 $9$ 年已经过去）；
• 部落将等待第 $36$ 年的第六个迹象（因为第五个迹象已经在第 $18$ 年出现）。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
 
using namespace std;
typedef long long LL;
const int N = 1010;
int a[N];
 
int main()
{
	int t;
	cin >> t;
	while (t--){
		LL n, pre = 1;
		cin >> n;
		
		for (int i = 1; i <= n; i++) {
			LL x;
			cin >> x;
			if (i == 1) pre = x;
			else {
				if (x > pre) pre = x;
				else if (x < pre) {
					if (pre % x != 0) pre = ceil(1.0 * pre / x) * x;
					else pre = (pre / x + 1) * x; 
				}
				else pre = pre * 2;
			}
		}
		cout << pre << '\n';
	}
	return 0;

C. LR-remainders

Problem - C - Codeforces

You are given an array $a$ of length $n$, a positive integer $m$, and a string of commands of length $n$. Each command is either the character ‘L’ or the character ‘R’.

Process all $n$ commands in the order they are written in the string $s$. Processing a command is done as follows:

• First, output the remainder of the product of all elements of the array $a$ when divided by $m$.
• Then, if the command is ‘L’, remove the leftmost element from the array $a$, if the command is ‘R’, remove the rightmost element from the array $a$.

Note that after each move, the length of the array $a$ decreases by $1$, and after processing all commands, it will be empty.

Write a program that will process all commands in the order they are written in the string $s$ (from left to right).

Input

The first line contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases in the input. Then descriptions of $t$ test cases follow.

Each test case of the input is given by three lines.

The first line contains two integers $n$ and $m$ ($1 \le n \le 2\cdot10^5, 1 \le m \le 10^4$) — the initial length of the array $a$ and the value to take the remainder by.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^4$) — the elements of the array $a$.

The third line contains a string $s$ consisting of $n$ characters ‘L’ and ‘R’.

It is guaranteed that the sum of the values of $n$ for all test cases in a test does not exceed $2\cdot10^5$.

Output

For each test case, output $n$ integers $b_1, b_2, \dots, b_n$, where $b_i$ is the remainder when dividing the product of all elements of the current state of the array $a$ by $m$ at the beginning of the execution of the $i$-th command.

Example

input

4
4 6
3 1 4 2
LRRL
5 1
1 1 1 1 1
LLLLL
6 8
1 2 3 4 5 6
RLLLRR
1 10000
10000
R

output

0 2 4 1 
0 0 0 0 0 
0 0 0 4 4 4 
0 

Note

In the first test case of the example:

• $3 \cdot 1 \cdot 4 \cdot 2 \bmod 6 = 24 \bmod 6 = 0$;
• $s_1 = \text{L}$, so we remove the first element and get the array $[1, 4, 2]$;
• $1 \cdot 4 \cdot 2 \bmod 6 = 8 \bmod 6 = 2$;
• $s_2 = \text{R}$, so we remove the last element and get the array $[1, 4]$;
• $1 \cdot 4 \bmod 6 = 4 \bmod 6 = 4$;
• $s_3 = \text{R}$, so we remove the last element and get the array $[1]$;
• $1 \bmod 6 = 1$;
• $s_4 = \text{L}$, so we remove the first element and get an empty array.

翻译

您将获得一个长度为 $n$ 的数组 $a$ 、一个正整数 $m$ 和一个长度为 $n$ 的命令字符串。每个命令要么是字符“L”，要么是字符“R”。

按照它们在字符串 $s$ 中的写入顺序处理所有 $n$ 命令。处理命令的过程如下：

• 首先，输出数组 $a$ 所有元素的乘积除以 $m$ 后的余数。
• 然后，如果命令是“L”，则从数组 $a$ 中删除最左边的元素，如果命令是“R”，则从数组 $a$ 中删除最右边的元素。

请注意，每次移动后，数组 $a$ 的长度都会减少 $1$ ，处理完所有命令后，它将为空。

编写一个程序，按照字符串 $s$ 中写入的顺序(从左到右)处理所有命令。

输入

第一行包含一个整数 $t$ ( $1 \le t \le 10^4$ ) — 输入中的测试用例数。然后是 $t$ 个测试用例的描述。

输入的每个测试用例由三行给出。

第一行包含两个整数 $n$ 和 $m$ ( $1 \le n \le 2\cdot10^5, 1 \le m \le 10^4$ ) — 数组 $a$ 的初始长度和取余数的值。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ( $1 \le a_i \le 10^4$ ) — 数组 $a$ 的元素。

第三行包含一个字符串 $s$ ，由 $n$ 个字符“L”和“R”组成。

保证一次测试中所有测试用例的 $n$ 值之和不超过 $2\cdot10^5$ 。

输出

对于每个测试用例，输出 $n$ 个整数 $b_1, b_2, \dots, b_n$ ，其中 $b_i$ 是执行第 $i$ 条命令时，将数组 $a$ 当前状态的所有元素的乘积除以 $m$ 后的余数。

Example

input

4
4 6
3 1 4 2
LRRL
5 1
1 1 1 1 1
LLLLL
6 8
1 2 3 4 5 6
RLLLRR
1 10000
10000
R

output

0 2 4 1 
0 0 0 0 0 
0 0 0 4 4 4 
0 

注意

在示例的第一个测试用例中：

• $3 \cdot 1 \cdot 4 \cdot 2 \bmod 6 = 24 \bmod 6 = 0$ ;
• $s_1 = \text{L}$ ，因此我们删除第一个元素并得到数组 $[1, 4, 2]$ ;
• $1 \cdot 4 \cdot 2 \bmod 6 = 8 \bmod 6 = 2$ ;
• $s_2 = \text{R}$ ，因此我们删除最后一个元素并得到数组 $[1, 4]$ ;
• $1 \cdot 4 \bmod 6 = 4 \bmod 6 = 4$ ;
• $s_3 = \text{R}$ ，因此我们删除最后一个元素并得到数组 $[1]$ ;
• $1 \bmod 6 = 1$ ;
• $s_4 = \text{L}$ ，因此我们删除第一个元素并得到一个空数组。

思路

​ 我们可以选择先沿着缩减区间的步骤走到终点，再从终点一步一步走回来，这和递归的思路很像。

​ 考虑递归，先沿着操作递归到终点。然后返回的时候返回区间乘积的余数，顺便记录每个位置的余数，之后顺序输出即可。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <set>
#include <vector>
 
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
int n, m;
int a[N];
string s;
vector<int> ans;
 
LL print(int x, int l, int r) {
	if (x >= n) return 1;
	LL tmp;
	if (s[x] == 'L') tmp = a[l] * print(x + 1, l + 1, r) % m;
	else tmp = a[r] * print(x + 1, l, r - 1) % m;
	ans.push_back(tmp);
	return tmp;	 
} 
void solve() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> a[i];
	cin >> s;
	ans.clear();
	print(0, 1, n);
	for (auto it = ans.rbegin(); it != ans.rend(); it++) cout << *it << " ";
	cout << '\n';
}
int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int _;
	cin >> _;
	while (_--) {
		solve();
	}
	return 0;
}

D. Card Game

Problem - d - Codeforces

Two players are playing an online card game. The game is played using a 32-card deck. Each card has a suit and a rank. There are four suits: clubs, diamonds, hearts, and spades. We will encode them with characters ‘C’, ‘D’, ‘H’, and ‘S’, respectively. And there are 8 ranks, in increasing order: ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’.

Each card is denoted by two letters: its rank and its suit. For example, the 8 of Hearts is denoted as 8H.

At the beginning of the game, one suit is chosen as the trump suit.

In each round, players make moves like this: the first player places one of his cards on the table, and the second player must beat this card with one of their cards. After that, both cards are moved to the discard pile.

A card can beat another card if both cards have the same suit and the first card has a higher rank than the second. For example, 8S can beat 4S. Additionally, a trump card can beat any non-trump card, regardless of the rank of the cards, for example, if the trump suit is clubs (‘C’), then 3C can beat 9D. Note that trump cards can be beaten only by the trump cards of higher rank.

There were $n$ rounds played in the game, so the discard pile now contains $2n$ cards. You want to reconstruct the rounds played in the game, but the cards in the discard pile are shuffled. Find any possible sequence of $n$ rounds that might have been played in the game.

Input

The first line contains integer $t$ ($1 \le t \le 100$) — the number of test cases. Then $t$ test cases follow.

The first line of a test case contains the integer number $n$ ($1\le n\le 16$).

The second line of a test case contains one character, the trump suit. It is one of “CDHS”.

The third line of a test case contains the description of $2n$ cards. Each card is described by a two-character string, the first character is the rank of the card, which is one of “23456789”, and the second one is the suit of the card, which is one of “CDHS”. All cards are different.

Output

For each test case print the answer to it:

• Print $n$ lines. In each line, print the description of two cards, in the same format as in the input: the first card that was played by the first player, and then the card that was used by the second player to beat it.
• If there is no solution, print a single line “IMPOSSIBLE”.

If there are multiple solutions, print any of them.

Example

input

8
3
S
3C 9S 4C 6D 3S 7S
2
C
3S 5D 9S 6H
1
H
6C 5D
1
S
7S 3S
1
H
9S 9H
1
S
9S 9H
1
C
9D 8H
2
C
9C 9S 6H 8C

output

3C 4C
6D 9S
3S 7S
IMPOSSIBLE
IMPOSSIBLE
3S 7S
9S 9H
9H 9S
IMPOSSIBLE
6H 9C
9S 8C

翻译

两名玩家正在玩一款在线纸牌游戏。游戏使用一副 32 张牌的牌组进行。每张牌都有花色和等级。共有四种花色：梅花、方块、红心和黑桃。我们将分别用字符“C”、“D”、“H”和“S”对它们进行编码。并且有 8 个等级，按递增顺序排列：“2”、“3”、“4”、“5”、“6”、“7”、“8”、“9”。

每张牌用两个字母表示：等级和花色。例如，红心 8 表示为 8H。

游戏开始时，会选择一个花色作为王牌花色。

在每一轮中，玩家的行动如下：第一个玩家将一张牌放在桌子上，第二个玩家必须用一张牌打败这张牌。之后，两张牌都移到弃牌堆。

如果两张牌的花色相同，且第一张牌的等级高于第二张牌，则一张牌可以击败另一张牌。例如，8S 可以击败 4S。此外，王牌可以击败任何非王牌，无论牌的等级如何，例如，如果王牌花色为梅花（“C”），则 3C 可以击败 9D。请注意，只有等级较高的王牌才能击败王牌。

游戏中进行了 $n$ 轮，因此弃牌堆现在包含 $2n$ 张牌。您想重建游戏中进行的轮次，但弃牌堆中的牌已被洗牌。找出游戏中可能进行的任何 $n$ 轮的可能序列。

输入

第一行包含整数 $t$ ( $1 \le t \le 100$ ) — 测试用例的数量。接下来是 $t$ 个测试用例。

测试用例的第一行包含整数 $n$ ( $1\le n\le 16$ )。

测试用例的第二行包含一个字符，即王牌花色。它是“CDHS”之一。

测试用例的第三行包含 $2n$ 张牌的描述。每张牌都由两个字符的字符串描述，第一个字符是牌的等级，是“23456789”之一，第二个字符是牌的花色，是“CDHS”之一。所有牌都是不同的。

输出

对于每个测试案例，打印其答案：

• 打印 $n$ 行。在每一行中，打印两张牌的描述，格式与输入相同：第一个玩家打出的第一张牌，然后是第二个玩家用来击败它的牌。
• 如果没有解决方案，则打印一行“IMPOSSIBLE”。

如果有多个解决方案，则打印其中任何一个。

Example

input

8
3
S
3C 9S 4C 6D 3S 7S
2
C
3S 5D 9S 6H
1
H
6C 5D
1
S
7S 3S
1
H
9S 9H
1
S
9S 9H
1
C
9D 8H
2
C
9C 9S 6H 8C

output

3C 4C
6D 9S
3S 7S
IMPOSSIBLE
IMPOSSIBLE
3S 7S
9S 9H
9H 9S
IMPOSSIBLE
6H 9C
9S 8C

思路

​ 这道题目的基本思路还是蛮清晰的，但是实际处理过程比较复杂：

​ 要注意到两个东西：

​ 王牌花色可以无视点数打败其他花色的牌
​ 每种牌只有一张，每张牌互不相同
​ 所以一个很明显的思路就是先顺序输出其他花色，两个两个输出，其他花色剩一张就用王牌花色凑一张，最后输出王牌花色。所以无解的判定条件很明显，就是其他花色中 奇数张的花色 的个数不超过王牌花色牌个数即可。因为题目给的是偶数张牌，所以不需要是否是奇数张牌。

​ 考虑如何输出，不难想到用set存储每张牌，开4个set存储四种花色。不过输出的时候判断每种花色是不是王牌花色比较麻烦。可以输入的时候直接把王牌花色的牌放到单独的set中，不放到4个set对应的花色中，其他花色的牌正常放即可。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <set>
 
using namespace std;
typedef long long LL;
int n;
char c;
 
 
void COUT(int x, int color = 0){
	cout << x << (color ? " CDHS"[color] : c) << " ";
}
int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int t;
	cin >> t;
	while (t--){
		cin >> n >> c;
		n *= 2;
		set<int> s[5], t;
		for (int i = 1; i <= n;i ++) {
			string tmp;
			cin >> tmp;
			if (tmp[1] == c) t.insert(tmp[0] - '0');
			else {
				switch(tmp[1]){
					case 'C': s[1].insert(tmp[0] - '0');break;
					case 'D': s[2].insert(tmp[0] - '0');break;
					case 'H': s[3].insert(tmp[0] - '0');break;
					case 'S': s[4].insert(tmp[0] - '0');break;
				}
			}
		}
 
		if (t.size() >= (s[1].size() % 2) + (s[2].size() % 2) + (s[3].size() % 2) + (s[4].size() % 2)){
			for (int i = 1; i <= 4; i++) {
				while (!s[i].empty()) {
					COUT(*s[i].begin(), i);
					s[i].erase(s[i].begin());
					
					if (s[i].empty()) {
						COUT(*t.begin());
						t.erase(t.begin());
					} else {
						COUT(*s[i].begin(), i);
						s[i].erase(s[i].begin());
					}
					cout << '\n';
				}
			}
			while (!t.empty()) {
				COUT(*t.begin());
				t.erase(t.begin());
				COUT(*t.begin());
				t.erase(t.begin());
				cout << '\n';
			}
		} else {
			cout << "IMPOSSIBLE\n";
		}
		
	}
	return 0;
}

E. Final Countdown

Problem - E - Codeforces

You are in a nuclear laboratory that is about to explode and destroy the Earth. You must save the Earth before the final countdown reaches zero.

The countdown consists of $n$ ($1 \le n \le 4 \cdot 10^5$) mechanical indicators, each showing one decimal digit. You noticed that when the countdown changes its state from $x$ to $x-1$, it doesn’t happen in one move. Instead, each change of a single digit takes one second.

So, for example, if the countdown shows 42, then it will change to 41 in one second, because only one digit is changed, but if the countdown shows 2300, then it will change to 2299 in three seconds, because the three last digits are changed.

Find out how much time is left before the countdown reaches zero.

Input

The first line of input contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Then the descriptions of the test cases follow.

The first line of each test case contains a single integer $n$ ($1\le n\le 4\cdot 10^5$).

The second line contains a string of $n$ digits, the current state of the countdown. It is guaranteed that at least one digit is not zero.

The sum of $n$ for all tests does not exceed $4\cdot 10^5$.

Output

For each test case, print a single integer without leading zeroes, the number of seconds left before the countdown reaches zero. Note that this number may be huge.

Example

input

5
2
42
5
12345
2
99
4
0005
27
456480697259671309012631002

output

46
13715
108
5
507200774732968121125145546

Note

In the first example, there are four changes that take 2 seconds: 40 to 39, 30 to 29, 20 to 19, and 10 to 09, other changes take 1 second each. So the total time is $2\cdot 4 + 1\cdot(42-4) = 46$.

翻译

你身处一个即将爆炸并摧毁地球的核实验室。你必须在最终倒计时归零之前拯救地球。

倒计时由 $n$ ( $1 \le n \le 4 \cdot 10^5$ ) 个机械指示器组成，每个指示器显示一位十进制数字。你注意到，当倒计时将其状态从 $x$ 更改为 $x-1$ 时，它并不是一次性发生的。相反，每次更改一位数字都需要一秒钟。

因此，例如，如果倒计时显示 42，那么它将在一秒钟内变为 41，因为只有一位数字发生了变化，但如果倒计时显示 2300，那么它将在三秒内变为 2299，因为最后三位数字发生了变化。

找出倒计时归零前还剩多少时间。

输入

输入的第一行包含一个整数 $t$ ( $1 \le t \le 10^4$ ) — 测试用例的数量。然后是测试用例的描述。

每个测试用例的第一行包含一个整数 $n$ ( $1\le n\le 4\cdot 10^5$ )。

第二行包含一串 $n$ 位数字，表示倒计时的当前状态。保证至少有一位数字不为零。

所有测试的 $n$ 之和不超过 $4\cdot 10^5$ 。

输出

对于每个测试用例，打印一个不带前导零的整数，即倒计时到零之前剩余的秒数。请注意，这个数字可能很大。

Example

input

5
2
42
5
12345
2
99
4
0005
27
456480697259671309012631002

output

46
13715
108
5
507200774732968121125145546

注意

在第一个示例中，有四次更改需要 2 秒：40 到 39、30 到 29、20 到 19 以及 10 到 09，其他更改每次需要 1 秒。因此总时间为 $2\cdot 4 + 1\cdot(42-4) = 46$ 。

思路

​ 考虑到只要有一位退位就会用掉一秒（假设把个位上的数减一也看作退一位），而减一的逆过程就是加一，被减数减 1 11 退位的次数和减数加 1 11 产生的进位的次数是相同的，因此我们把一个数不断减一到零产生的退位次数相当于给零加一不断加到这个数产生的进位次数。

​ 而不断加 1 11，每个数位上会产生多少进位，也就是变化呢。以12345举例，不难发现个位会变化12345次，十位会变化1234次，百位会变化123次，千位变化12次，各位变化1次，总的变化次数就是 12345 + 1234 + 123 + 12 + 1 = 13715 12345+1234+123+12+1=1371512345+1234+123+12+1=13715 次。

​ 不过直接写高精实现高精加法的话，由于 ：
$$
n = 4 ∗ 1 0^5\
一个高精数是 n 位，n 个高精数相加的复杂度是 n^2,会TLE。
$$
把式子写成竖式的形式，就会发现一个规律：

12345
1234
123
12

————

13715
由于是对称的，个位上的数相当于前五个 数位上每个数的和 模10（多出来的数进位了），十位上的数相当于前四位上每个数的和加上来自个位的进位 模10，同理百千万位上的数。

​ 这提示我们可以用前缀和算出每个数位上的数，最后处理一下进位即可，前缀和 和 处理进位的时间复杂度是 O ( n ) 的，而前缀和不会超 9 ∗ 4 ∗ 1 0^5^，不会爆int。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
 
using namespace std;
typedef long long LL;
const int N = 4e5 + 10;
LL sum[N];
 
int main()
{
	int t;
	cin >> t;
	while (t--) {
		int n;
		string s;
 
		cin >> n >> s;
		sum[0] = 0;
		for (int i = 1; i <= n; i++) {
			sum[i] = sum[i - 1] + (s[i - 1] - '0'); 	
		}
		for (int i = n; i >= 1; i--) {
			sum[i - 1] += sum[i] / 10;
			sum[i] %= 10;
		}
		
		bool flag = false;
		for (int i = 0; i <= n; i++) {
			if (sum[i] != 0 || flag == true){
				flag = true;
				cout << sum[i];
			}
		}
		cout << '\n';
	}
	return 0;
}