XPSC 08 | Week 3 | Topicwise | STL - 2 Apr 21, 2026

Problem A. Sereja and Suffixes

Time Limit 1000 ms
Mem Limit 262144 kB
Input File stdin
Output File stdout

Problem Link

Sereja has an array a, consisting of n integers a1, a2, ..., an. The boy cannot sit and do

nothing, he decided to study an array. Sereja took a piece of paper and wrote out m integers
l1, l2, ..., lm (1 ≤ li ≤ n). For each number li he wants to know how many distinct
numbers are staying on the positions li, li + 1, ..., n. Formally, he want to find the number

of distinct numbers among al , al + 1, ..., an.?

i i

Sereja wrote out the necessary array elements but the array was so large and the boy was so
pressed for time. Help him, find the answer for the described question for each li.

Input

The first line contains two integers n and m (1 ≤ n, m ≤ 105). The second line contains

n integers a1, a2, ..., an (1 ≤ ai ≤ 105) — the array elements.

Next m lines contain integers l1, l2, ..., lm. The i-th line contains integer li (1 ≤ li ≤ n).

Output

Print m lines — on the i-th line print the answer to the number li.

Examples

Page 1 of 31
-
 XPSC 08 | Week 3 | Topicwise | STL - 2 Apr 21, 2026

Input Output

10 10 6
1 2 3 4 1 2 3 4 100000 99999 6
1 6
2 6
3 6
4 5
5 4
6 3
7 2
8 1
9
10

Page 2 of 31
-
 XPSC 08 | Week 3 | Topicwise | STL - 2 Apr 21, 2026

Problem B. Polycarp Training

Time Limit 2000 ms
Mem Limit 262144 kB

Problem Link

Polycarp wants to train before another programming competition. During the first day of
his training he should solve exactly 1 problem, during the second day — exactly 2 problems,
during the third day — exactly 3 problems, and so on. During the k -th day he should solve k
problems.

Polycarp has a list of n contests, the i-th contest consists of ai problems. During each day
​

Polycarp has to choose exactly one of the contests he didn't solve yet and solve it. He solves
exactly k problems from this contest. Other problems are discarded from it. If there are no
contests consisting of at least k problems that Polycarp didn't solve yet during the k -th day,
then Polycarp stops his training.

How many days Polycarp can train if he chooses the contests optimally?

Input

The first line of the input contains one integer n (1 ≤ n ≤ 2 ⋅ 105 ) — the number of
contests.

The second line of the input contains n integers a1 , a2 , … , an (1

​ ​ ​
≤ ai ≤ 2 ⋅ 105 ) — the
​

number of problems in the i-th contest.

Output

Print one integer — the maximum number of days Polycarp can train if he chooses the
contests optimally.

Examples

Page 3 of 31
-
 XPSC 08 | Week 3 | Topicwise | STL - 2 Apr 21, 2026

Input Output

4 3
3 1 4 1

Input Output

3 1
1 1 1

Input Output

5 2
1 1 1 2 2

Page 4 of 31
-
 XPSC 08 | Week 3 | Topicwise | STL - 2 Apr 21, 2026

Problem C. Epic Transformation

Time Limit 2000 ms
Mem Limit 262144 kB

Problem Link

You are given an array a of length n consisting of integers. You can apply the following
operation, consisting of several steps, on the array a zero or more times:

you select two different numbers in the array ai and aj ;

​ ​

you remove i-th and j -th elements from the array.

For example, if n = 6 and a = [1, 6, 1, 1, 4, 4], then you can perform the following sequence
of operations:

select i = 1, j = 5. The array a becomes equal to [6, 1, 1, 4];

select i = 1, j = 2. The array a becomes equal to [1, 4].

What can be the minimum size of the array after applying some sequence of operations to
it?

Input

The first line contains a single integer t (1 ≤ t ≤ 104 ). Then t test cases follow.

The first line of each test case contains a single integer n (1 ≤ n ≤ 2 ⋅ 105 ) is length of the
array a.

The second line of each test case contains n integers a1 , a2 , … , an (1

​ ​ ​
≤ ai ≤ 109 ).
​

It is guaranteed that the sum of n over all test cases does not exceed 2 ⋅ 105 .

Output

For each test case, output the minimum possible size of the array after applying some
sequence of operations to it.

Examples
Page 5 of 31
-
 XPSC 08 | Week 3 | Topicwise | STL - 2 Apr 21, 2026

Input Output

5 0
6 0
1 6 1 1 4 4 2
2 1
1 2 0
2
1 1
5
4 5 4 5 4
6
2 3 2 1 3 1

Page 6 of 31
-
 XPSC 08 | Week 3 | Topicwise | STL - 2 Apr 21, 2026

Problem D. Train and Queries

Time Limit 3000 ms
Mem Limit 262144 kB

Problem Link

Along the railroad there are stations indexed from 1 to 109 . An express train always travels
along a route consisting of n stations with indices u1 , u2 , … , un , where (1
​ ​ ​
≤ ui ≤ 109 ). The​

train travels along the route from left to right. It starts at station u1 , then stops at station u2
​ ​

, then at u3 , and so on. Station un — the terminus.

​ ​

It is possible that the train will visit the same station more than once. That is, there may be
duplicates among the values u1 , u2 , … , un .
​ ​ ​

You are given k queries, each containing two different integers aj and bj (1 ​ ​
≤ aj , bj ≤ 109 ).
​ ​

For each query, determine whether it is possible to travel by train from the station with
index aj to the station with index bj .
​ ​

For example, let the train route consist of 6 of stations with indices [3, 7, 1, 5, 1, 4] and give
3 of the following queries:

a 1 = 3, b 1 = 5
​ ​

It is possible to travel from station 3 to station 5 by taking a section of the route

consisting of stations [3, 7, 1, 5]. Answer: YES.

a 2 = 1, b 2 = 7
​ ​

You cannot travel from station 1 to station 7 because the train cannot travel in the
opposite direction. Answer: NO.

a3 = 3, b3 = 10
​ ​

It is not possible to travel from station 3 to station 10 because station 10 is not part of
the train's route. Answer: NO.

Input

The first line of the input contains an integer t (1 ≤ t ≤ 104 ) —the number of test cases in
the test.

Page 7 of 31
-
 XPSC 08 | Week 3 | Topicwise | STL - 2 Apr 21, 2026

The descriptions of the test cases follow.

The first line of each test case is empty.

The second line of each test case contains two integers: n and k (1 ≤ n ≤ 2 ⋅ 105 , 1 ≤ k ≤
2 ⋅ 105 ) —the number of stations the train route consists of and the number of queries.

The third line of each test case contains exactly n integers u1 , u2 , … , un (1

​ ​ ​ ≤ ui ≤ 109 ).
​

The values u1 , u2 , … , un are not necessarily different.

​ ​ ​

The following k lines contain two different integers aj and bj (1

​ ​ ≤ aj , bj ≤ 109 ) describing
​ ​

the query with index j .

It is guaranteed that the sum of n values over all test cases in the test does not exceed 2 ⋅ 105
. Similarly, it is guaranteed that the sum of k values over all test cases in the test also does
not exceed 2 ⋅ 105

Output

For each test case, output on a separate line:

YES, if you can travel by train from the station with index aj to the station with index
​

bj ​

NO otherwise.

You can output YES and NO in any case (for example, strings yEs, yes, Yes and YES will be
recognized as a positive response).

Examples

Page 8 of 31
-
 XPSC 08 | Week 3 | Topicwise | STL - 2 Apr 21, 2026

Input Output

3 YES
NO
NO
6 3 YES
3 7 1 5 1 4 YES
3 5 NO
1 7 NO
3 10 YES
YES
NO
3 3 YES
1 2 1
2 1
1 2
4 5

7 5
2 1 1 1 2 4 4
1 3
1 4
2 1
4 1
1 2

Note

The first test case is explained in the problem statement.

Page 9 of 31
-
 XPSC 08 | Week 3 | Topicwise | STL - 2 Apr 21, 2026

Problem E. Berpizza
Time Limit 5000 ms
Mem Limit 524288 kB

Problem Link

Monocarp and Polycarp are working as waiters in Berpizza, a pizzeria located near the
center of Bertown. Since they are waiters, their job is to serve the customers, but they
choose whom they serve first differently.

At the start of the working day, there are no customers at the Berpizza. They come there one
by one. When a customer comes into the pizzeria, she sits and waits for Monocarp or
Polycarp to serve her. Monocarp has been working in Berpizza for just two weeks, so
whenever he serves a customer, he simply chooses the one who came to Berpizza first, and
serves that customer.

On the other hand, Polycarp is an experienced waiter at Berpizza, and he knows which
customers are going to spend a lot of money at the pizzeria (and which aren't) as soon as he
sees them. For each customer, Polycarp estimates the amount of money this customer can
spend, and when he serves a customer, he chooses the one that is expected to leave the most
money at Berpizza (in case there are several such customers, he chooses the one who came
first among them).

Obviously, no customer can be served twice, so Monocarp and Polycarp choose which
customer to serve only among those who haven't been served yet.

When the number of customers gets really high, it becomes difficult for both Monocarp and
Polycarp to choose the customer they are going to serve. Your task is to write a program that
makes these choices for them. Formally, your program should be able to process three types
of queries:

1 m — a customer comes to Berpizza, and Polycarp estimates the amount of money

that they will spend as m;
2 — Monocarp serves a customer which came to the pizzeria first;
3 — Polycarp serves a customer which is expected to spend the largest amount of
money at the pizzeria (if there are several such customers, the one that came to the
pizzeria first is chosen).

Page 10 of 31
-
 XPSC 08 | Week 3 | Topicwise | STL - 2 Apr 21, 2026

For each query of types 2 and 3, report the number of the customer who was served (the
customers are numbered in the order they come to the pizzeria, starting from 1).

Input

The first line contains one integer q (2 ≤ q ≤ 5 ⋅ 105 ) — the number of queries.

Then q lines follow, each describing a query in one of the following formats:

1 m (1 ≤ m ≤ 5 ⋅ 105 ) — a customer comes to Berpizza, and Polycarp estimates the

amount of money that they will spend as m;
2 — Monocarp serves a customer which came to the pizzeria first;
3 — Polycarp serves a customer which is expected to spend the largest amount of
money at the pizzeria (if there are multiple such customers, the one that came to the
pizzeria first is chosen).

Queries of type 2 and 3 are asked only when there exists at least one customer that hasn't
been served yet. There is at least one query of type 2 or 3 in the input.

Output

For each query of type 2 or 3, print one integer — the number of the customer that has been
served in that event. The customers are numbered in the order in which they come to the
pizzeria, starting from 1.

Examples
Input Output

8 2 1 3 4
1 8
1 10
1 6
3
2
1 9
2
3

Page 11 of 31
-
 XPSC 08 | Week 3 | Topicwise | STL - 2 Apr 21, 2026

Input Output

6 2 1 3
1 8
1 10
1 8
3
3
3

Input Output

8 1 2 3
1 103913
3
1 103913
1 103913
3
1 103913
1 103913
2

Page 12 of 31
-
 XPSC 08 | Week 3 | Topicwise | STL - 2 Apr 21, 2026

Problem F. Dora and Search

Time Limit 1000 ms
Mem Limit 262144 kB

Problem Link

As you know, the girl Dora is always looking for something. This time she was given a
permutation, and she wants to find such a subsegment of it that none of the elements at its
ends is either the minimum or the maximum of the entire subsegment. More formally, you
are asked to find the numbers l and r (1 ≤ l ≤ r ≤ n) such that al  = min(al , al+1 , … , ar ),
​ ​ ​ ​

al 
​
= max(al , al+1 , … , ar ) and ar 
​ ​ ​
= min(al , al+1 , … , ar ), ar 
​ ​ ​
= max(al , al+1 , … , ar ).
​ ​ ​

A permutation of length n is an array consisting of n distinct integers from 1 to n in any

order. For example, [2, 3, 1, 5, 4] is a permutation, but [1, 2, 2] is not a permutation (2 occurs
twice in the array) and [1, 3, 4] is also not a permutation (n = 3, but 4 is present in the
array).

Help Dora find such a subsegment, or tell her that such a subsegment does not exist.

Input

Each test consists of multiple test cases. The first line contains a single integer t (1 ≤t≤
4
10 ) — the number of test cases. Description of the test cases follows.

For each test case, the first line contains one integer n (1 ≤ n ≤ 2 ⋅ 105 ) — the length of
permutation.

The second line contains n distinct integers a1 , a2 , … , an (1

​ ​ ​
≤ ai ≤ n) — the elements of
​

permutation.

It is guarented that the sum of n over all test cases doesn't exceed 2 ⋅ 105 .

Output

For each test case, output −1 if the desired subsegment does not exist.

Otherwise, output two indexes l, r such that [al , al+1 , … , ar ] satisfies all conditions.
​ ​ ​

Page 13 of 31
-
 XPSC 08 | Week 3 | Topicwise | STL - 2 Apr 21, 2026

If there are several solutions, then output any of them.

Examples
Input Output

4 -1
3 1 4
1 2 3 2 6
4 -1
2 1 4 3
7
1 3 2 4 6 5 7
6
2 3 6 5 4 1

Note

In the first and fourth test cases, it can be shown that there are no desired subsegments.

In the second test case, the subsegment [1, 4] satisfies all the conditions, because
max(a1 , a2 , a3 , a4 ) = 4, min(a1 , a2 , a3 , a4 ) = 1, as we see, all the conditions are met.
​ ​ ​ ​ ​ ​ ​ ​

In the third test case, the subsegment [2, 6] also satisfies all the conditions described.

Page 14 of 31
-
 XPSC 08 | Week 3 | Topicwise | STL - 2 Apr 21, 2026

Problem G. Numeric String Template

Time Limit 2000 ms
Mem Limit 262144 kB

Problem Link

Kristina has an array a, called a template, consisting of n integers. She also has m strings,
each consisting only of lowercase Latin letters. The strings are numbered from 1 to m. She
wants to check which strings match the template.

A string s is considered to match the template if all of the following conditions are
simultaneously satisfied:

The length of the string s is equal to the number of elements in the array a.
The same numbers from a correspond to the same symbols from s. So, if ai ​
= aj , then
​

si = sj for (1 ≤ i, j ≤ n).
​ ​

The same symbols from s correspond to the same numbers from a. So, if si = sj , then​ ​

ai = aj for (1 ≤ i, j ≤ n).
​ ​

In other words, there must be a one-to-one correspondence between the characters of the
string and the elements of the array.

For example, if a = [3, 5, 2, 1, 3], then the string "abfda" matches the template, while the
string "afbfa" does not, since the character "f" corresponds to both numbers 1 and 5.

Input

The first line of input contains a single integer t (1 ≤ t ≤ 104 ) — the number of test cases.

The following descriptions are for the test cases.

The first line of each test case contains a single integer n (1 ≤ n ≤ 2 ⋅ 105 ) — the number of
elements in the array a.

The second line of each test case contains exactly n integers ai (−109
​
≤ ai ≤ 109 ) — the
​

elements of the array a.

The third line of each test case contains a single integer m (1 ≤ m ≤ 2 ⋅ 105 ) — the number
of strings to check for template matching.

Page 15 of 31
-
 XPSC 08 | Week 3 | Topicwise | STL - 2 Apr 21, 2026

Following are m strings, each containing a non-empty string sj (1 ​ ≤ ∣sj ∣ ≤ 2 ⋅ 105 ),

​

consisting of lowercase Latin letters.

It is guaranteed that the sum of n across all test cases does not exceed 2 ⋅ 105 , and that the
sum of the lengths of all strings does not exceed 2 ⋅ 105 .

Output

For each test case, output m lines. On the i-th line (1 ≤ i ≤ m) output:

"YES", if the string with index i matches the template;

"NO" otherwise.

You may output the answer in any case (for example, the strings "yEs", "yes", "Yes", and
"YES" will be recognized as a positive answer).

Examples
Input Output

3 YES
5 NO
3 5 2 1 3 YES
2 NO
abfda NO
afbfa NO
2 YES
1 2 NO
3 YES
ab
abc
aa
4
5 -3 5 -3
4
aaaa
bcbc
aba
cbcb

Note

The first test case is explained in the problem statement.

Page 16 of 31
-
 XPSC 08 | Week 3 | Topicwise | STL - 2 Apr 21, 2026

Problem H. Box Fitting

Time Limit 1000 ms
Mem Limit 262144 kB

Problem Link

You are given n rectangles, each of height 1. Each rectangle's width is a power of 2 (i. e. it
can be represented as 2x for some non-negative integer x).

You are also given a two-dimensional box of width W . Note that W may or may not be a
power of 2. Moreover, W is at least as large as the width of the largest rectangle.

You have to find the smallest height of this box, such that it is able to fit all the given
rectangles. It is allowed to have some empty space left in this box after fitting all the
rectangles.

You cannot rotate the given rectangles to make them fit into the box. Moreover, any two
distinct rectangles must not overlap, i. e., any two distinct rectangles must have zero
intersection area.

See notes for visual explanation of sample input.

Input

The first line of input contains one integer t (1 ≤ t ≤ 5 ⋅ 103 ) — the number of test cases.
Each test case consists of two lines.

For each test case:

the first line contains two integers n (1 ≤ n ≤ 105 ) and W (1 ≤ W ≤ 109 );

the second line contains n integers w1 , w2 , … , wn (1 ≤ wi ≤ 106 ), where wi is the
​ ​ ​ ​ ​

width of the i-th rectangle. Each wi is a power of 2;

​

n
additionally, max wi ≤ W .
​ ​

i=1

The sum of n over all test cases does not exceed 105 .

Output

Page 17 of 31
-
 XPSC 08 | Week 3 | Topicwise | STL - 2 Apr 21, 2026

Output t integers. The i-th integer should be equal to the answer to the i-th test case — the
smallest height of the box.

Examples
Input Output

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

Note

For the first test case in the sample input, the following figure shows one way to fit the
given five rectangles into the 2D box with minimum height:

In the figure above, the number inside each rectangle is its width. The width of the 2D box is
16 (indicated with arrow below). The minimum height required for the 2D box in this case is
2 (indicated on the left).

In the second test case, you can have a minimum height of three by keeping two blocks (one
each of widths eight and two) on each of the three levels.

Page 18 of 31
-
 XPSC 08 | Week 3 | Topicwise | STL - 2 Apr 21, 2026

Problem I. 2-Letter Strings

Time Limit 2000 ms
Mem Limit 262144 kB

Problem Link

Given n strings, each of length 2, consisting of lowercase Latin alphabet letters from 'a' to
'k', output the number of pairs of indices (i, j) such that i < j and the i-th string and the j
-th string differ in exactly one position.

In other words, count the number of pairs (i, j) (i< j ) such that the i-th string and the j -
th string have exactly one position p (1 ≤ p ≤ 2) such that si p 
= sj p .
​ ​ ​ ​

The answer may not fit into 32-bit integer type, so you should use 64-bit integers like long
long in C++ to avoid integer overflow.

Input

The first line of the input contains a single integer t (1 ≤ t ≤ 100) — the number of test
cases. The description of test cases follows.

The first line of each test case contains a single integer n (1 ≤ n ≤ 105 ) — the number of
strings.

Then follows n lines, the i-th of which containing a single string si of length 2, consisting
​

of lowercase Latin letters from 'a' to 'k'.

It is guaranteed that the sum of n over all test cases does not exceed 105 .

Output

For each test case, print a single integer — the number of pairs (i, j) (i
< j ) such that the i-
th string and the j -th string have exactly one position p (1 ≤ p ≤ 2) such that si p 
= sj p .
​ ​ ​ ​

Please note, that the answer for some test cases won't fit into 32-bit integer type, so you
should use at least 64-bit integer type in your programming language (like long long for
C++).

Page 19 of 31
-
 XPSC 08 | Week 3 | Topicwise | STL - 2 Apr 21, 2026

Examples
Input Output

4 5
6 6
ab 0
cb 6
db
aa
cc
ef
7
aa
bb
cc
ac
ca
bb
aa
4
kk
kk
ab
ab
5
jf
jf
jk
jk
jk

Note

For the first test case the pairs that differ in exactly one position are: ("ab", "cb"), ("ab",
"db"), ("ab", "aa"), ("cb", "db") and ("cb", "cc").

For the second test case the pairs that differ in exactly one position are: ("aa", "ac"),
("aa", "ca"), ("cc", "ac"), ("cc", "ca"), ("ac", "aa") and ("ca", "aa").

For the third test case, the are no pairs satisfying the conditions.

Page 20 of 31
-
 XPSC 08 | Week 3 | Topicwise | STL - 2 Apr 21, 2026

Problem J. Numbers on Whiteboard

Time Limit 2000 ms
Mem Limit 262144 kB

Problem Link

Numbers 1, 2, 3, … n (each integer from 1 to n once) are written on a board. In one

a+b
operation you can erase any two numbers a and b from the board and write one integer 2 ​

rounded up instead.

You should perform the given operation n − 1 times and make the resulting number that
will be left on the board as small as possible.

For example, if n = 4, the following course of action is optimal:

1. choose a = 4 and b = 2, so the new number is 3, and the whiteboard contains [1, 3, 3];
2. choose a = 3 and b = 3, so the new number is 3, and the whiteboard contains [1, 3];
3. choose a = 1 and b = 3, so the new number is 2, and the whiteboard contains [2].

It's easy to see that after n − 1 operations, there will be left only one number. Your goal is to
minimize it.

Input

The first line contains one integer t (1 ≤ t ≤ 1000) — the number of test cases.

The only line of each test case contains one integer n (2 ≤ n ≤ 2 ⋅ 105 ) — the number of
integers written on the board initially.

It's guaranteed that the total sum of n over test cases doesn't exceed 2 ⋅ 105 .

Output

For each test case, in the first line, print the minimum possible number left on the board
after n − 1 operations. Each of the next n − 1 lines should contain two integers — numbers
a and b chosen and erased in each operation.

Page 21 of 31
-
 XPSC 08 | Week 3 | Topicwise | STL - 2 Apr 21, 2026

Examples
Input Output

1 2
4 2 4
3 3
3 1

Page 22 of 31
-
 XPSC 08 | Week 3 | Topicwise | STL - 2 Apr 21, 2026

Problem K. The Strict Teacher (Hard Version)

Time Limit 1500 ms
Mem Limit 262144 kB

Problem Link

This is the hard version of the problem. The only differences between the two versions are
the constraints on m and q . In this version, m, q ≤ 105 . You can make hacks only if both
versions of the problem are solved.

Narek and Tsovak were busy preparing this round, so they have not managed to do their
homework and decided to steal David's homework. Their strict teacher noticed that David
has no homework and now wants to punish him. She hires other teachers to help her catch
David. And now m teachers together are chasing him. Luckily, the classroom is big, so David
has many places to hide.

The classroom can be represented as a one-dimensional line with cells from 1 to n,

inclusive.

At the start, all m teachers and David are in distinct cells. Then they make moves. During
each move

David goes to an adjacent cell or stays at the current one.

Then, each of the m teachers simultaneously goes to an adjacent cell or stays at the
current one.

This continues until David is caught. David is caught if any of the teachers (possibly more
than one) is located in the same cell as David. Everyone sees others' moves, so they all act
optimally.

Your task is to find how many moves it will take for the teachers to catch David if they all act
optimally.

Acting optimally means the student makes his moves in a way that maximizes the number
of moves the teachers need to catch him; and the teachers coordinate with each other to
make their moves in a way that minimizes the number of moves they need to catch the
student.

Page 23 of 31
-
 XPSC 08 | Week 3 | Topicwise | STL - 2 Apr 21, 2026

Also, as Narek and Tsovak think this task is easy, they decided to give you q queries on
David's position.

Input

In the first line of the input, you are given a single integer t (1 ≤ t ≤ 105 ) — the number of
test cases. The description of each test case follows.

In the first line of each test case, you are given three integers n, m, and q (3 ≤ n ≤ 109 ,
1 ≤ m, q ≤ 105 ) — the number of cells on the line, the number of teachers, and the number
of queries.

In the second line of each test case, you are given m distinct integers b1 , b2 , … , bm (1
​ ​ ​ ≤
bi ≤ n) — the cell numbers of the teachers.
​

In the third line of each test case, you are given q integers a1 , a2 , … , aq (1
​ ​ ​ ≤ a i ≤ n) —
​

David's cell number for every query.

It is guaranteed that for any i, j such that 1 ≤ i ≤ m and 1 ≤ j ≤ q , bi 

= aj .
​ ​

It is guaranteed that the sum of values of m over all test cases does not exceed 2 ⋅ 105 .

It is guaranteed that the sum of values of q over all test cases does not exceed 2 ⋅ 105 .

Output

For each test case, output q lines, the i-th of them containing the answer of the i-th query.

Examples
Input Output

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

Note

Page 24 of 31
-
 XPSC 08 | Week 3 | Topicwise | STL - 2 Apr 21, 2026

In the only query of the first example, the student can run to cell 1. It will take the teacher
five moves to reach from cell 6 to cell 1, so the answer is 5.

In the second query of the second example, the student can just stay at cell 3. The teacher,
initially located in cell 4, can reach cell 3 in one move. Therefore, the answer is 1.

Page 25 of 31
-
 XPSC 08 | Week 3 | Topicwise | STL - 2 Apr 21, 2026

Problem L. Update Queries

Time Limit 2000 ms
Mem Limit 262144 kB

Problem Link

Let's consider the following simple problem. You are given a string s of length n, consisting
of lowercase Latin letters, as well as an array of indices ind of length m (1 ≤ indi ≤ n) and
​

a string c of length m, consisting of lowercase Latin letters. Then, in order, you perform the
update operations, namely, during the i-th operation, you set sindi ​
​
= ci . Note that you
​

perform all m operations from the first to the last.

Of course, if you change the order of indices in the array ind and/or the order of letters in
the string c, you can get different results. Find the lexicographically smallest string s that
can be obtained after m update operations, if you can rearrange the indices in the array ind
and the letters in the string c as you like.

A string a is lexicographically less than a string b if and only if one of the following
conditions is met:

a is a prefix of b, but a =
 b;
in the first position where a and b differ, the symbol in string a is earlier in the
alphabet than the corresponding symbol in string b.

Input

Each test consists of several sets of input data. The first line contains a single integer t (1 ≤
4
t ≤ 10 ) — the number of sets of input data. Then follows their description.

The first line of each set of input data contains two integers n and m (1 ≤ n, m ≤ 105 ) —
the length of the string s and the number of updates.

The second line of each set of input data contains a string s of length n, consisting of
lowercase Latin letters.

The third line of each set of input data contains m integers ind1 , ind2 , … , indm (1
​ ​ ​
≤
indi ≤ n) — the array of indices ind.
​

The fourth line of each set of input data contains a string c of length m, consisting of
lowercase Latin letters.
Page 26 of 31
-
 XPSC 08 | Week 3 | Topicwise | STL - 2 Apr 21, 2026

It is guaranteed that the sum of n over all sets of input data does not exceed 2 ⋅ 105 .
Similarly, the sum of m over all sets of input data does not exceed 2 ⋅ 105 .

Output

For each set of input data, output the lexicographically smallest string s that can be
obtained by rearranging the indices in the array ind and the letters in the string c as you
like.

Examples
Input Output

4 b
1 2 cwoz
a abdcmbn
1 1 ccdeefo
cb
4 4
meow
1 2 1 4
zcwz
7 4
abacaba
1 3 5 7
damn
7 10
traktor
7 6 5 4 3 2 1 6 4 2
codeforces

Note

In the first set of input data, you can leave the array ind and the string c unchanged and
simply perform all operations in that order.

= [1, 1, 4, 2] and c = "zczw". Then

In the second set of input data, you can set the array ind
the string s will change as follows: meow → zeow → ceow → ceoz → cwoz .

= "admn".
In the third set of input data, you can leave the array ind unchanged and set c
Then the string s will change as follows: abacaba → abacaba → abdcaba → abdcmba →
abdcmbn.

Page 27 of 31
-
 XPSC 08 | Week 3 | Topicwise | STL - 2 Apr 21, 2026

Problem M. Powering the Hero (hard version)

Time Limit 2000 ms
Mem Limit 262144 kB

Problem Link

This is a hard version of the problem. It differs from the easy one only by constraints on n
and t.

There is a deck of n cards, each of which is characterized by its power. There are two types of
cards:

a hero card, the power of such a card is always equal to 0;

a bonus card, the power of such a card is always positive.

You can do the following with the deck:

take a card from the top of the deck;

if this card is a bonus card, you can put it on top of your bonus deck or discard;
if this card is a hero card, then the power of the top card from your bonus deck is added
to his power (if it is not empty), after that the hero is added to your army, and the used
bonus discards.

Your task is to use such actions to gather an army with the maximum possible total power.

Input

The first line of input data contains single integer t (1 ≤ t ≤ 104 ) — the number of test
cases in the test.

The first line of each test case contains one integer n (1 ≤ n ≤ 2 ⋅ 105 ) — the number of
cards in the deck.

The second line of each test case contains n integers s1 , s2 , … , sn (0

​ ​ ​
≤ si ≤ 109 ) — card
​

powers in top-down order.

It is guaranteed that the sum of n over all test cases does not exceed 2 ⋅ 105 .

Output
Page 28 of 31
-
 XPSC 08 | Week 3 | Topicwise | STL - 2 Apr 21, 2026

Output t numbers, each of which is the answer to the corresponding test case — the
maximum possible total power of the army that can be achieved.

Examples
Input Output

5 6
5 6
3 3 3 0 0 8
6 9
0 3 3 0 0 3 4
7
1 2 3 0 4 5 0
7
1 2 5 0 4 3 0
5
3 1 0 0 4

Note

In the first sample, you can take bonuses 1 and 2. Both hero cards will receive 3 power. If
you take all the bonuses, one of them will remain unused.

In the second sample, the hero's card on top of the deck cannot be powered up, and the rest
can be powered up with 2 and 3 bonuses and get 6 total power.

In the fourth sample, you can take bonuses 1, 2, 3, 5 and skip the bonus 6, then the hero 4
will be enhanced with a bonus 3 by 5, and the hero 7 with a bonus 5 by 4. 4 + 5 = 9.

Page 29 of 31
-
 XPSC 08 | Week 3 | Topicwise | STL - 2 Apr 21, 2026

Problem N. Matryoshkas
Time Limit 2000 ms
Mem Limit 262144 kB

Problem Link

Matryoshka is a wooden toy in the form of a painted doll, inside which you can put a similar
doll of a smaller size.

A set of nesting dolls contains one or more nesting dolls, their sizes are consecutive positive
integers. Thus, a set of nesting dolls is described by two numbers: s — the size of a smallest
nesting doll in a set and m — the number of dolls in a set. In other words, the set contains
sizes of s, s + 1, … , s + m − 1 for some integer s and m (s, m > 0).

You had one or more sets of nesting dolls. Recently, you found that someone mixed all your
sets in one and recorded a sequence of doll sizes — integers a1 , a2 , … , an .
​ ​ ​

You do not remember how many sets you had, so you want to find the minimum number of
sets that you could initially have.

For example, if a given sequence is a = [2, 2, 3, 4, 3, 1]. Initially, there could be 2 sets:

the first set consisting of 4 nesting dolls with sizes [1, 2, 3, 4];
a second set consisting of 2 nesting dolls with sizes [2, 3].

According to a given sequence of sizes of nesting dolls a1 , a2 , … , an , determine the

​ ​ ​

minimum number of nesting dolls that can make this sequence.

Each set is completely used, so all its nesting dolls are used. Each element of a given
sequence must correspond to exactly one doll from some set.

Input

The first line of input data contains a single integer t (1 ≤ t ≤ 104 ) — the number of test
cases.

The description of the test cases follows.

The first line of each test case contains one integer n (1 ≤ n ≤ 2 ⋅ 105 ) — the total number
of matryoshkas that were in all sets.

Page 30 of 31
-
 XPSC 08 | Week 3 | Topicwise | STL - 2 Apr 21, 2026

The second line of each test case contains n integers a1 , a2 , … , an (1

​ ​ ​ ≤ ai ≤ 109 ) — the
​

sizes of the matryoshkas.

It is guaranteed that the sum of values of n over all test cases does not exceed 2 ⋅ 105 .

Output

For each test case, print one integer k — the minimum possible number of matryoshkas
sets.

Examples
Input Output

10 2
6 1
2 2 3 4 3 1 6
5 2
11 8 7 10 9 2
6 2
1000000000 1000000000 1000000000 2
1000000000 1000000000 1000000000 2
8 4
1 1 4 4 2 3 2 3 3
6
1 2 3 2 3 4
7
10 11 11 12 12 13 13
7
8 8 9 9 10 10 11
8
4 14 5 15 6 16 7 17
8
5 15 6 14 8 12 9 11
5
4 2 2 3 4

Note

The first test case is described in the problem statement.

In the second test case, all matryoshkas could be part of the same set with minimum size
s = 7.

In the third test case, each matryoshka represents a separate set.

Page 31 of 31
-