1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
WTF?
Contest: April Fools Day Contest 2013
Difficulty rating: 1700
Tags: *special, graph matchings, implementation, trees

Input format:
The input contains between 1 and 10 lines, i-th line contains an integer number xi (0 ≤ xi ≤ 9).

Output format:
Output a single real number. The answer is considered to be correct if its absolute or relative error does not exceed 10 - 4.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
3
0
1
1

Example output:
0.666667

Editorial:
Orange
Contest: April Fools Day Contest 2013
Difficulty rating: 1400
Tags: *special, implementation

Input format:
The first line of the input is a string (between 1 and 50 characters long, inclusive). Each character will be a letter of English alphabet, lowercase or uppercase.

The second line of the input is an integer between 0 and 26, inclusive.

Output format:
Output the required string.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
AprilFool
14

Example output:
AprILFooL

Editorial:
HQ
Contest: April Fools Day Contest 2013
Difficulty rating: 2500
Tags: *special, constructive algorithms

The famous joke programming language HQ9+ has only 4 commands. In this problem we will explore its subset — a language called HQ...

Input format:
The only line of the input is a string between 1 and 106 characters long.

Output format:
Output "Yes" or "No".

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
The rest of the problem statement was destroyed by a stray raccoon. We are terribly sorry for the inconvenience.

Example input:
HHHH

Example output:
Yes

Example input:
HQHQH

Example output:
No

Editorial:
Greedy Petya
Contest: April Fools Day Contest 2013
Difficulty rating: 2800
Tags: *special, dfs and similar, graphs, greedy

Petya is an unexperienced programming contestant. Recently he has come across the following problem:

You are given a non-directed graph which consists of n nodes and m edges. Your task is to determine whether the graph contains a Hamiltonian path.

Petya wrote a quick bug-free code which he believes solves this problem. After that Petya decided to give this problem for April Fools Day contest. Unfortunately, Petya might have made a mistake, and it's quite possible that his algorithm is wrong. But this isn't a good excuse to leave the contest without submitting this problem, is it?

Input format:
The first line contains two integers n, m (1 ≤ n ≤ 20; 0 ≤ m ≤ 400). Next m lines contain pairs of integers vi, ui (1 ≤ vi, ui ≤ n).

Output format:
Follow the format of Petya's code output.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
2 3
1 2
2 1
1 1

Example output:
Yes

Example input:
3 0

Example output:
No

Editorial:
Creating Words
Contest: Codeforces Round 952 (Div. 4)
Difficulty rating: 800
Tags: implementation, strings

Matthew is given two strings $$$a$$$ and $$$b$$$, both of length $$$3$$$. He thinks it's particularly funny to create two new words by swapping the first character of $$$a$$$ with the first character of $$$b$$$. He wants you to output $$$a$$$ and $$$b$$$ after the swap.

Note that the new words may not necessarily be different.

Input format:
The first line contains $$$t$$$ ($$$1 \leq t \leq 100$$$)  — the number of test cases.

The first and only line of each test case contains two space-separated strings, $$$a$$$ and $$$b$$$, both of length $$$3$$$. The strings only contain lowercase Latin letters.

Output format:
For each test case, after the swap, output $$$a$$$ and $$$b$$$, separated by a space.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Example input:
6
bit set
cat dog
hot dog
uwu owo
cat cat
zzz zzz

Example output:
sit bet
dat cog
dot hog
owu uwo
cat cat
zzz zzz

Editorial:
Maximum Multiple Sum
Contest: Codeforces Round 952 (Div. 4)
Difficulty rating: 800
Tags: brute force, math, number theory

Given an integer $$$n$$$, find an integer $$$x$$$ such that:

- $$$2 \leq x \leq n$$$.
- The sum of multiples of $$$x$$$ that are less than or equal to $$$n$$$ is maximized. Formally, $$$x + 2x + 3x + \dots + kx$$$ where $$$kx \leq n$$$ is maximized over all possible values of $$$x$$$.

Input format:
The first line contains $$$t$$$ ($$$1 \leq t \leq 100$$$) — the number of test cases.

Each test case contains a single integer $$$n$$$ ($$$2 \leq n \leq 100$$$).

Output format:
For each test case, output an integer, the optimal value of $$$x$$$. It can be shown there is only one unique answer.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
For $$$n = 3$$$, the possible values of $$$x$$$ are $$$2$$$ and $$$3$$$. The sum of all multiples of $$$2$$$ less than or equal to $$$n$$$ is just $$$2$$$, and the sum of all multiples of $$$3$$$ less than or equal to $$$n$$$ is $$$3$$$. Therefore, $$$3$$$ is the optimal value of $$$x$$$.

For $$$n = 15$$$, the optimal value of $$$x$$$ is $$$2$$$. The sum of all multiples of $$$2$$$ less than or equal to $$$n$$$ is $$$2 + 4 + 6 + 8 + 10 + 12 + 14 = 56$$$, which can be proven to be the maximal over all other possible values of $$$x$$$.

Example input:
2
3
15

Example output:
3
2

Editorial:
Good Prefixes
Contest: Codeforces Round 952 (Div. 4)
Difficulty rating: 1000
Tags: greedy

Alex thinks some array is good if there exists some element that can be represented as the sum of all other elements (the sum of all other elements is $$$0$$$ if there are no other elements). For example, the array $$$[1,6,3,2]$$$ is good since $$$1+3+2=6$$$. Furthermore, the array $$$[0]$$$ is also good. However, the arrays $$$[1,2,3,4]$$$ and $$$[1]$$$ are not good.

Alex has an array $$$a_1,a_2,\ldots,a_n$$$. Help him count the number of good non-empty prefixes of the array $$$a$$$. In other words, count the number of integers $$$i$$$ ($$$1 \le i \le n$$$) such that the length $$$i$$$ prefix (i.e. $$$a_1,a_2,\ldots,a_i$$$) is good.

Input format:
The first line of the input contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of elements in the array.

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$0 \le a_i \le 10^9$$$) — the elements of the array.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, output a single integer — the number of good non-empty prefixes of the array $$$a$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the fourth test case, the array has five prefixes:

- prefix $$$[0]$$$ is a good array, as mentioned in the statement;
- prefix $$$[0, 1]$$$ is not a good array, since $$$0 \ne 1$$$;
- prefix $$$[0, 1, 2]$$$ is not a good array, since $$$0 \ne 1 + 2$$$, $$$1 \ne 0 + 2$$$ and $$$2 \ne 0 + 1$$$;
- prefix $$$[0, 1, 2, 1]$$$ is a good array, since $$$2 = 0 + 1 + 1$$$;
- prefix $$$[0, 1, 2, 1, 4]$$$ is a good array, since $$$4 = 0 + 1 + 2 + 1$$$.

As you can see, three of them are good, so the answer is $$$3$$$.

Example input:
7
1
0
1
1
4
1 1 2 0
5
0 1 2 1 4
7
1 1 0 3 5 2 12
7
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 294967296
10
0 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 589934592

Example output:
1
0
3
3
4
1
2

Editorial:
Manhattan Circle
Contest: Codeforces Round 952 (Div. 4)
Difficulty rating: 900
Tags: implementation, math

Given a $$$n$$$ by $$$m$$$ grid consisting of '.' and '#' characters, there exists a whole manhattan circle on the grid. The top left corner of the grid has coordinates $$$(1,1)$$$, and the bottom right corner has coordinates $$$(n, m)$$$.

Point ($$$a, b$$$) belongs to the manhattan circle centered at ($$$h, k$$$) if $$$|h - a| + |k - b| < r$$$, where $$$r$$$ is a positive constant.

On the grid, the set of points that are part of the manhattan circle is marked as '#'. Find the coordinates of the center of the circle.

Input format:
The first line contains $$$t$$$ ($$$1 \leq t \leq 1000$$$)  — the number of test cases.

The first line of each test case contains $$$n$$$ and $$$m$$$ ($$$1 \leq n \cdot m \leq 2 \cdot 10^5$$$) — the height and width of the grid, respectively.

The next $$$n$$$ lines contains $$$m$$$ characters '.' or '#'. If the character is '#', then the point is part of the manhattan circle.

It is guaranteed the sum of $$$n \cdot m$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$, and there is a whole manhattan circle on the grid.

Output format:
For each test case, output the two integers, the coordinates of the center of the circle.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
6
5 5
.....
.....
..#..
.....
.....
5 5
..#..
.###.
#####
.###.
..#..
5 6
......
......
.#....
###...
.#....
1 1
#
5 6
...#..
..###.
.#####
..###.
...#..
2 10
..........
...#......

Example output:
3 3
3 3
4 2
1 1
3 4
2 4

Editorial:
Secret Box
Contest: Codeforces Round 952 (Div. 4)
Difficulty rating: 1200
Tags: brute force, combinatorics, math

Ntarsis has a box $$$B$$$ with side lengths $$$x$$$, $$$y$$$, and $$$z$$$. It lies in the 3D coordinate plane, extending from $$$(0,0,0)$$$ to $$$(x,y,z)$$$.

Ntarsis has a secret box $$$S$$$. He wants to choose its dimensions such that all side lengths are positive integers, and the volume of $$$S$$$ is $$$k$$$. He can place $$$S$$$ somewhere within $$$B$$$ such that:

- $$$S$$$ is parallel to all axes.
- every corner of $$$S$$$ lies on an integer coordinate.

$$$S$$$ is magical, so when placed at an integer location inside $$$B$$$, it will not fall to the ground.

Among all possible ways to choose the dimensions of $$$S$$$, determine the maximum number of distinct locations he can choose to place his secret box $$$S$$$ inside $$$B$$$. Ntarsis does not rotate $$$S$$$ once its side lengths are selected.

Input format:
The first line consists of an integer $$$t$$$, the number of test cases ($$$1 \leq t \leq 2000$$$). The description of the test cases follows.

The first and only line of each test case contains four integers $$$x, y, z$$$ and $$$k$$$ ($$$1 \leq x, y, z \leq 2000$$$, $$$1 \leq k \leq x \cdot y \cdot z$$$).

It is guaranteed the sum of all $$$x$$$, sum of all $$$y$$$, and sum of all $$$z$$$ do not exceed $$$2000$$$ over all test cases.

Note that $$$k$$$ may not fit in a standard 32-bit integer data type.

Output format:
For each test case, output the answer as an integer on a new line. If there is no way to select the dimensions of $$$S$$$ so it fits in $$$B$$$, output $$$0$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
For the first test case, it is optimal to choose $$$S$$$ with side lengths $$$2$$$, $$$2$$$, and $$$2$$$, which has a volume of $$$2 \cdot 2 \cdot 2 = 8$$$. It can be shown there are $$$8$$$ ways to put $$$S$$$ inside $$$B$$$.

The coordinate with the least $$$x$$$, $$$y$$$, and $$$z$$$ values for each possible arrangement of $$$S$$$ are:

1. $$$(0, 0, 0)$$$
2. $$$(1, 0, 0)$$$
3. $$$(0, 1, 0)$$$
4. $$$(0, 0, 1)$$$
5. $$$(1, 0, 1)$$$
6. $$$(1, 1, 0)$$$
7. $$$(0, 1, 1)$$$
8. $$$(1, 1, 1)$$$

The arrangement of $$$S$$$ with a coordinate of $$$(0, 0, 0)$$$ is depicted below:

For the second test case, $$$S$$$ with side lengths $$$2$$$, $$$3$$$, and $$$3$$$ are optimal.

Example input:
7
3 3 3 8
3 3 3 18
5 1 1 1
2 2 2 7
3 4 2 12
4 3 1 6
1800 1800 1800 4913000000

Example output:
8
2
5
0
4
4
1030301

Editorial:
Final Boss
Contest: Codeforces Round 952 (Div. 4)
Difficulty rating: 1500
Tags: binary search, data structures

You are facing the final boss in your favorite video game. The boss enemy has $$$h$$$ health. Your character has $$$n$$$ attacks. The $$$i$$$'th attack deals $$$a_i$$$ damage to the boss but has a cooldown of $$$c_i$$$ turns, meaning the next time you can use this attack is turn $$$x + c_i$$$ if your current turn is $$$x$$$. Each turn, you can use all attacks that are not currently on cooldown, all at once. If all attacks are on cooldown, you do nothing for the turn and skip to the next turn.

Initially, all attacks are not on cooldown. How many turns will you take to beat the boss? The boss is beaten when its health is $$$0$$$ or less.

Input format:
The first line contains $$$t$$$ ($$$1 \leq t \leq 10^4$$$)  – the number of test cases.

The first line of each test case contains two integers $$$h$$$ and $$$n$$$ ($$$1 \leq h, n \leq 2 \cdot 10^5$$$) – the health of the boss and the number of attacks you have.

The following line of each test case contains $$$n$$$ integers $$$a_1, a_2, ..., a_n$$$ ($$$1 \leq a_i \leq 2 \cdot 10^5$$$) – the damage of your attacks.

The following line of each test case contains $$$n$$$ integers $$$c_1, c_2, ..., c_n$$$ ($$$1 \leq c_i \leq 2 \cdot 10^5$$$) – the cooldown of your attacks.

It is guaranteed that the sum of $$$h$$$ and $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, output an integer, the minimum number of turns required to beat the boss.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
For the first test case, you can use attacks $$$1$$$ and $$$2$$$ on the first turn, dealing $$$3$$$ damage in total, and slaying the boss.

For the second case, you can beat the boss in $$$3$$$ turns by using the following attacks:

Turn $$$1$$$: Use attacks $$$1$$$ and $$$2$$$, dealing $$$3$$$ damage to the boss. The boss now has $$$2$$$ health left.

Turn $$$2$$$: Use attack $$$2$$$, dealing $$$1$$$ damage to the boss. The boss now has $$$1$$$ health left.

Turn $$$3$$$: Use attack $$$1$$$, dealing $$$2$$$ damage to the boss. The boss now has $$$-1$$$ health left. Since its health is less than or equal to $$$0$$$, you beat the boss.

For the sixth test case: remember to use 64-bit integers as the answer can get large.

Example input:
8
3 2
2 1
2 1
5 2
2 1
2 1
50 3
5 6 7
5 6 7
50 3
2 2 2
3 3 3
90000 2
200000 200000
1 1
100000 1
1
200000
6 7
3 2 3 2 3 1 2
6 5 9 5 10 7 7
21 6
1 1 1 1 1 1
5 5 8 10 7 6

Example output:
1
3
15
25
1
19999800001
1
21

Editorial:
D-Function
Contest: Codeforces Round 952 (Div. 4)
Difficulty rating: 1600
Tags: combinatorics, math, number theory

Let $$$D(n)$$$ represent the sum of digits of $$$n$$$. For how many integers $$$n$$$ where $$$10^{l} \leq n < 10^{r}$$$ satisfy $$$D(k \cdot n) = k \cdot D(n)$$$? Output the answer modulo $$$10^9+7$$$.

Input format:
The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) – the number of test cases.

Each test case contains three integers $$$l$$$, $$$r$$$, and $$$k$$$ ($$$0 \leq l < r \leq 10^9$$$, $$$1 \leq k \leq 10^9$$$).

Output format:
For each test case, output an integer, the answer, modulo $$$10^9 + 7$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
For the first test case, the only values of $$$n$$$ that satisfy the condition are $$$1$$$ and $$$2$$$.

For the second test case, the only values of $$$n$$$ that satisfy the condition are $$$1$$$, $$$10$$$, and $$$11$$$.

For the third test case, all values of $$$n$$$ between $$$10$$$ inclusive and $$$100$$$ exclusive satisfy the condition.

Example input:
6
0 1 4
0 2 7
1 2 1
1 2 3
582 74663 3
0 3 1

Example output:
2
3
90
12
974995667
999

Editorial:
Maximize the Largest Component (Easy Version)
Contest: Codeforces Round 952 (Div. 4)
Difficulty rating: 1700
Tags: brute force, data structures, dfs and similar, dsu, graphs, implementation

Easy and hard versions are actually different problems, so read statements of both problems completely and carefully. The only difference between the two versions is the operation.

Alex has a grid with $$$n$$$ rows and $$$m$$$ columns consisting of '.' and '#' characters. A set of '#' cells forms a connected component if from any cell in this set, it is possible to reach any other cell in this set by only moving to another cell in the set that shares a common side. The size of a connected component is the number of cells in the set.

In one operation, Alex selects any row $$$r$$$ ($$$1 \le r \le n$$$) or any column $$$c$$$ ($$$1 \le c \le m$$$), then sets every cell in row $$$r$$$ or column $$$c$$$ to be '#'. Help Alex find the maximum possible size of the largest connected component of '#' cells that he can achieve after performing the operation at most once.

Input format:
The first line of the input contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \cdot m \le 10^6$$$) — the number of rows and columns of the grid.

The next $$$n$$$ lines each contain $$$m$$$ characters. Each character is either '.' or '#'.

It is guaranteed that the sum of $$$n \cdot m$$$ over all test cases does not exceed $$$10^6$$$.

Output format:
For each test case, output a single integer — the maximum possible size of a connected component of '#' cells that Alex can achieve.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
In the second test case, it is optimal for Alex to set all cells in column $$$2$$$ to be '#'. Doing so will lead to the largest connected component of '#' having a size of $$$6$$$.

In the third test case, it is optimal for Alex to set all cells in row $$$2$$$ to be '#'. Doing so will lead to the largest connected component of '#' having a size of $$$9$$$.

In the fourth test case, it is optimal for Alex to set all cells in row $$$4$$$ to be '#'. Doing so will lead to the largest connected component of '#' having a size of $$$11$$$.

Example input:
6
1 1
.
4 2
..
#.
#.
.#
3 5
.#.#.
..#..
.#.#.
5 5
#...#
....#
#...#
.....
...##
6 6
.#..#.
#..#..
.#...#
#.#.#.
.#.##.
###..#
6 8
..#....#
.####.#.
###.#..#
.##.#.##
.#.##.##
#..##.#.

Example output:
1
6
9
11
15
30

Editorial:
Maximize the Largest Component (Hard Version)
Contest: Codeforces Round 952 (Div. 4)
Difficulty rating: 2200
Tags: data structures, dfs and similar, dp, dsu, implementation

Easy and hard versions are actually different problems, so read statements of both problems completely and carefully. The only difference between the two versions is the operation.

Alex has a grid with $$$n$$$ rows and $$$m$$$ columns consisting of '.' and '#' characters. A set of '#' cells forms a connected component if from any cell in this set, it is possible to reach any other cell in this set by only moving to another cell in the set that shares a common side. The size of a connected component is the number of cells in the set.

In one operation, Alex selects any row $$$r$$$ ($$$1 \le r \le n$$$) and any column $$$c$$$ ($$$1 \le c \le m$$$), then sets every cell in row $$$r$$$ and column $$$c$$$ to be '#'. Help Alex find the maximum possible size of the largest connected component of '#' cells that he can achieve after performing the operation at most once.

Input format:
The first line of the input contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \cdot m \le 10^6$$$) — the number of rows and columns of the grid.

The next $$$n$$$ lines each contain $$$m$$$ characters. Each character is either '.' or '#'.

It is guaranteed that the sum of $$$n \cdot m$$$ over all test cases does not exceed $$$10^6$$$.

Output format:
For each test case, output a single integer — the maximum possible size of a connected component of '#' cells that Alex can achieve.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
In the fourth test case, it is optimal for Alex to set all cells in row $$$4$$$ and column $$$2$$$ to be '#'. Doing so will lead to the largest connected component of '#' having a size of $$$16$$$.

In the fifth test case, it is optimal for Alex to set all cells in row $$$2$$$ and column $$$4$$$ to be '#'. Doing so will lead to the largest connected component of '#' having a size of $$$22$$$.

Example input:
6
1 1
.
4 2
..
#.
#.
.#
3 5
.#.#.
..#..
.#.#.
5 5
#...#
....#
#...#
.....
...##
6 6
.#..#.
#..#..
.#...#
#.#.#.
.#.##.
###..#
6 8
..#....#
.####.#.
###.#..#
.##.#.##
.#.##.##
#..##.#.

Example output:
1
7
11
16
22
36

Editorial:
Function Sum
Contest: Codeforces Round 841 (Div. 2) and Divide by Zero 2022
Difficulty rating: 2500
Tags: brute force, combinatorics, dp, fft, math

Suppose you have an integer array $$$a_1, a_2, \dots, a_n$$$.

Let $$$\operatorname{lsl}(i)$$$ be the number of indices $$$j$$$ ($$$1 \le j < i$$$) such that $$$a_j < a_i$$$.

Analogically, let $$$\operatorname{grr}(i)$$$ be the number of indices $$$j$$$ ($$$i < j \le n$$$) such that $$$a_j > a_i$$$.

Let's name position $$$i$$$ good in the array $$$a$$$ if $$$\operatorname{lsl}(i) < \operatorname{grr}(i)$$$.

Finally, let's define a function $$$f$$$ on array $$$a$$$ $$$f(a)$$$ as the sum of all $$$a_i$$$ such that $$$i$$$ is good in $$$a$$$.

Given two integers $$$n$$$ and $$$k$$$, find the sum of $$$f(a)$$$ over all arrays $$$a$$$ of size $$$n$$$ such that $$$1 \leq a_i \leq k$$$ for all $$$1 \leq i \leq n$$$ modulo $$$998\,244\,353$$$.

Input format:
The first and only line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 50$$$; $$$2 \leq k < 998\,244\,353$$$).

Output format:
Output a single integer — the sum of $$$f$$$ over all arrays $$$a$$$ of size $$$n$$$ modulo $$$998\,244\,353$$$.

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

Note:
In the first test case:

$$$f([1,1,1]) = 0$$$$$$f([2,2,3]) = 2 + 2 = 4$$$$$$f([1,1,2]) = 1 + 1 = 2$$$$$$f([2,3,1]) = 2$$$$$$f([1,1,3]) = 1 + 1 = 2$$$$$$f([2,3,2]) = 2$$$$$$f([1,2,1]) = 1$$$$$$f([2,3,3]) = 2$$$$$$f([1,2,2]) = 1$$$$$$f([3,1,1]) = 0$$$$$$f([1,2,3]) = 1$$$$$$f([3,1,2]) = 1$$$$$$f([1,3,1]) = 1$$$$$$f([3,1,3]) = 1$$$$$$f([1,3,2]) = 1$$$$$$f([3,2,1]) = 0$$$$$$f([1,3,3]) = 1$$$$$$f([3,2,2]) = 0$$$$$$f([2,1,1]) = 0$$$$$$f([3,2,3]) = 2$$$$$$f([2,1,2]) = 1$$$$$$f([3,3,1]) = 0$$$$$$f([2,1,3]) = 2 + 1 = 3$$$$$$f([3,3,2]) = 0$$$$$$f([2,2,1]) = 0$$$$$$f([3,3,3]) = 0$$$$$$f([2,2,2]) = 0$$$

Adding up all of these values, we get $$$28$$$ as the answer.

Example input:
3 3

Example output:
28

Example input:
5 6

Example output:
34475

Editorial:
Let's try to write a brute force solution of this using combinatorics. Let's say that $$$a[i]=t$$$ now we will try to see that in how many permutations this is contributing towards the answer. Using combinatorics, it can be calculated as $$$$$$F(t) = t \cdot {\sum_{i=1}^n \sum_{x=0}^{i-1} \sum_{y = x+1}^{n-i} \left( \binom{i-1}{x} (t-1)^{x} (K+1-t)^{i-1-x} \cdot \binom{n-i}{y} (K-t)^{y} \cdot t^{n-i-y} \right)} $$$$$$.
Here $$$x$$$ represents $$$\operatorname{lsl}(i)$$$ and y represents $$$\operatorname{grr}(i)$$$.
Let $$$$$$P(u) = {\sum_{t=1}^u F(t)} $$$$$$ be a polynomial whose degree will be $$$\le n+2$$$. And now our answer will be $$$P(k)$$$.
Now, we can evaluate this polynomial for smaller values (by brute force) and will use the technique of polynomial interpolation to find the answer.