BUET Inter University

Programming Contest 2023

https://toph.co/c/buet-inter-university-2023
Schedule
The contest will run for 5h0m0s.

Authors
The authors of this contest are Ahmed.032170, Anachor, Arghya, Iftekhar_Hakim,
longlongint, LUMBERJACK_MAN, N3710rD, neo11235, Sk_Sabit, tbs_sajal15, and
upobir.

Rules
This contest is formatted as per the official rules of ICPC Regional Programming
Contests.

You can use Bash 5.0, Brainf*ck, C# Mono 6.0, C++11 GCC 7.4, C++14 GCC 8.3, C++17
GCC 9.2, C++20 GCC 12.1, C11 GCC 12.1, C11 GCC 9.2, Common Lisp SBCL 2.0, Erlang
22.3, Free Pascal 3.0, Go 1.18, Grep 3.7, Haskell 8.6, Java 1.8, Kotlin 1.1, Lua 5.4, Node.js
10.16, Perl 5.30, PHP 7.2, PyPy 7.1 (2.7), PyPy 7.1 (3.6), Python 2.7, Python 3.11, Python
3.7, Ruby 2.7, Ruby 3.2, Rust 1.57, Swift 5.3, and Whitespace in this contest.

Be fair, be honest. Plagiarism will result in disqualification. Judges’ decisions will be

final.

Notes
There are 12 challenges in this contest.

Please make sure this booklet contains all of the pages.

If you find any discrepencies between the printed copy and the problem statements in
Toph Arena, please rely on the later.

BUET Inter University Programming Contest 2023 | Toph 2 of 24

A. Satisfaction
You have vacation for the nextNN
N days. Each day you will either create a problem or
you will hold a contest with exactly one problem. Formally speaking, your action for
the next NN
N days can be described by a string of length NN
N containing characters ‘P’ and
‘C’. If theithi^{th} ithi^{th}
ith character is ‘P’ then you will be creating a problem on ith ithi^{th}
day, if ith
character is ‘C’ then you will hold a contest on that day with a problem that is created
before ithi^{th}
ith day and unused till then. Each problem has an interesting factor and each
xxx to a
contest has an importance factor. If you put a problem with interesting factor
contest of importance factor yy x×yx
y , then you get x × y satisfaction.
\times
You need to put problems to contests in suchya way that the sum of your satisfaction is
maximized. Also the interesting factor of the problems are non increasing as your are
not getting any sharper day by day. Input will be generated in a way that, for each
contest you will have at least one problem available and as you love contests, you will
not miss the chance to be the problem-setter in any contest.

Input
T(1≤T≤10000)T(1\le
First line contains number of test cases T (1 ≤ T ≤ 10000).
T\le
Each testcase starts with an integer N (1 ≤ N ≤ 106 ).
N(1≤N≤106)N(1\le
10000)
N\le
A(A[1]…
The next line contains a string A(A[1] NN
10^6) … A[N ]) containing N characters, each
character is either ‘P’ or ‘C’. A[N])A(A[1]…
A[N])
The next line contains NN
N space separated integersV[1],V[2],….,V[N]V[1],V[2],….,V[N]
V [1], V [2], … ., V [N ], ifA[i]=‘P’A[i]
A[i] =
‘P ’ then V[i]V[i] on=ith day,
V [i] denotes interesting factor of the problem that you create ithi^{th}
else V[i]V[i]
V [i] denotes importance factor of the contest on ithi^{th}
ith day. ‘P’

1≤i≤N1\le
For all 1 ≤ V [i] ≤ 106
≤ i ≤ N , 11≤V[i]≤1061\le
i\le V[i]
If ii<ji A[i]=A[j]=‘P’A[i]
< jNand A[i] =\le V[i]≥V[j]V[i]
A[j] = ‘P ’ then V [i] ≥ V [j]
\lt = 10^6 \ge
A[j]that the sum of NN
It'sj guaranteed 106 .
all test cases does not exceed 10610^6
N overV[j]
=
Output ‘P’
For each case, output a single integer, which denotes the maximum satisfaction you
can get if you optimally place the problems in the contests.

BUET Inter University Programming Contest 2023 | Toph 3 of 24

Samples
Input Output
2 129
5 89
PPCPC
9 8 9 6 6
5
PPCPC
9 8 1 7 9

For the first testcase,

Answer is 9∗9+6∗8=1299*9
9 ∗ 9 + 6 ∗ 8 = 129. On the1st1^{st}
1st contest (day333) you will put the problem
created on+day 11
1 and on the 2nd2^{nd}
2nd contest (day 55
5) you will assign the problem created on
day 22
2. 6*8
=
129 testcase,
For the second
Answer is 8∗1+9∗9=898*1
8 ∗ 1 + 9 ∗ 9 = 89. On the1st1^{st} 33 3) you will put the problem
1st contest (day
created on+day 22
2 and on the 2nd2^{nd}
2 contest (day 55
nd
5) you will assign the problem created on
day 11
1. 9*9
=
89

BUET Inter University Programming Contest 2023 | Toph 4 of 24

B. Peculiar Partitioning II
aaa of length
You are given an array nn n. Each element of the array is a non-negative
integer less than 2k2^k
2k . You have to partition it into two non-empty sub-sequences XX
X and
YY
Y such that each element belongs to exactly one XXXYY of or Y . The score of such a
partitioning is given by(x1∧x2⋯
(x1 ∧ x2 ⋯ ∧ x∣X∣ ) ∨ (y1 ∧ y2 ⋯ ∧ y∣Y ∣ ). Here,∧\wedge
∧ denotes
the bitwise AND operation∧x∣X∣)∨(y1∧y2⋯
and ∨\vee
∨ denotes the bitwise OR operation.
∧y∣Y∣)
For each xx
x between 00 (x_1
0 and 2k−12^k-1
2k − 1, find the number of ways to partition the array such
that the score isxx \wedge
x. Since this number can be large, you only need to find it modulo
998244353998244353
998244353. x_2
\cdots
Two ways of partitioning \wedge
are considered different if and only if there exists a pair of
indices i,ji,
x_{|
i, j such that they are in the same part in one way, but in different parts in the
X|})
other. j
\vee
(y_1
Input \wedge
y_2
The first line contains two space separated integers, nn
n and kk
k.
\cdots\wedge
The second line contains nn
y_{|
n space-separated integers aa1,a2,⋯
1 , a2 , ⋯,an.a_1,a_2,\cdots
, an . ,a_n.
Y|})
Constraints

•2 ≤ n ≤ 3 × 105
2≤n≤3×1052
\leq
•1
1≤k≤181\leq
≤ k ≤ 18
n
k
• \leq
00≤ai<2k0
≤ ai < 2k
\leq
3\leq
18
\times
a_i
Output10^5
<2^k
Output 2k2^k
2k space separated integersf0,f1,⋯ ,f2k−1f_0,
f0 , f1 , ⋯ fxf_x
, f2k −1 . where, fx is the number of
ways, modulo 998244353998244353 f_1,such that the score is xx
998244353, to partition x.
\cdots,
f_{2^k-1}
Samples
Input Output
4 2 0 4 0 3
1 1 2 3

BUET Inter University Programming Contest 2023 | Toph 5 of 24

 Input Output
5 3 4 5 2 1 2 1 0 0
5 1 4 2 3

Input Output
2 1 0 1
0 1

BUET Inter University Programming Contest 2023 | Toph 6 of 24

C. The Very Last Exam
You have spent the last twenty years studying competitive programming. Now only one
exam stands between you and becoming the very best. You open the exam paper and see
a single problem.

You are given nn

n bags, each containing some distinct stones of varying weights. From
P/P /Q.
each bag, you can pick at most one stone. You are also given a target fraction
You have to pick stones so that their average weight is exactlyP/ QP/ways
P /Q. How many
can this be done so? Output the count of such ways. QP/ Q
Q
Note that two ways of picking stones are different if there is some bag from which you
pick a stone in one way but not in the other or if from some bag you pick different
stone (different stones can have same weight).

Input
First line of input will have a integer TT
T denoting the number of independent testcases.
Each testcase will start with a line containing one integer, nn
n denoting number of bags.
Next nn
n lines will contain the description of bags.
Each line will contain several space separated integers. They will start with an integer
kk
k denoting the number of stones in the bag. Nextkkk integers will denote the weights
PPP and
of the stones in the bag. Final line of the testcase will contain two integers QQQ
P//Q.
denoting the target fraction P
QP/
Constraints Q

•1
1≤T≤101
≤ T ≤ 10
\leq
•1 ≤ n ≤ 105
1≤n≤1051
T
\leq
• \leq
11≤k≤991
≤ k ≤ 99
n
10
\leq
• \leq
1≤1\leq 109
≤109\leq
1k ≤ weight of each stone ≤
10^5 10^9
• \leq ≤ P , Q ≤ 1018
11≤P,Q≤10181
99
\leq
• Product of (k
P, (k+1) 1012
+ 1) over all bags in a testcase will be at most 101210^{12}
Q (k+1)

BUET Inter University Programming Contest 2023 | Toph 7 of 24

 \leq
Output
10^{18}
For each testcase output the count of ways in a single line.

Samples
Input Output
2 8
2 5
2 1 1
2 1 1
1 1
3
2 2 3
3 1 4 2
3 3 2 1
5 2

In the first testcase, among the nine possible combinations of picking stones, one picks
none of the stones and other eight picks stones in such a way that the average is
= 11 .
1=111
exactly 1
=
\frac
1
1

BUET Inter University Programming Contest 2023 | Toph 8 of 24

D. Festive Shuffling
You are given a binary string SS
S and kk
k distinct indices to perform an operation.
The operation is like below:

You can shuffle the given indices any number of times (possibly zero).

SSS
You have to find out the maximum length of a palindromic subsequence of string
after shuffling.

Example of an operation: Say SS

S = “001110”, Let the indices be[1,
[1, 3, 5]. Then after the
operation the string content can be, 100110. 3,
5]
[1,
Input
3,
The first line of input contains a string SS
S and an integer kk
k 5]
kkk space separated integers
The next line will contain a1,a2,…,aka_1,
a1 , a2 , … , ak denoting the
a_2,
indices that you can shuffle, all of them are guaranteed to be distinct.
\ldots,
Constraints a_k

1≤∣S∣≤5001\le|
1 ≤ ∣S∣ ≤ 500
S|
00≤k≤∣S∣0
≤ k ≤ ∣S∣
\le500
\le
11≤ai≤∣S∣1\le
k ≤ ai ≤ ∣S∣
a_i\le
\le
||
Output
S|
S|
Output one line containing the output, the maximum length of any palindromic
subsequence after the operation.

Samples
Input Output
10010 2 5
1 2

BUET Inter University Programming Contest 2023 | Toph 9 of 24

E. Ankara Messi
It is Argentina vs Croatia in the football world cup semifinal of 2022 in a parallel universe.

The football field can be considered as an infinite 22

2- dimensional plane. Lionel Messi of
Argentina has the ball. He is at coordinate (x, 0). Joško Gvardiol, a defender of Croatia
(x − 1, 0). At any moment, Gvardiol 0)
is at (x−1, 111 unit
runs directly towards Messi at speed
0)
per second. Messi knows the movement(x,
strategy of Gvardiol. Messi himself has a
(x-1,0)
maximum speed of vv
v unit per second. 0)

11 1
Gvardiol will tackle Messi if the distance between them becomes strictly less than
unit. Gvardiol has a choice to foul Messi at a moment when Messi moves from a
position which is more than 1 unit away to a position which is exactly11
1 unit away from
Gvardiol. A dribble is a path on the field which Messi can take to move to coordinate
(0, 0) without getting tackled or fouled.
0)
Messi does not know if Gvardiol intends to foul or not. So to be safe, he plans his
(0,0)
dribble assuming that Gvardiol will foul him given the chance.

A dribble XX XXX if he knows

X is called boring if Messi can make a dribble shorter than
beforehand that Gvardiol won’t foul.

Messi wants to know the length of the shortest dribble which is not boring. It can be
proved that such a dribble exists under the given constraints.

Input
First line contains an integer TT ≤ T ≤ 5 × 104 ), the number of test cases.
(1≤T≤5×104)
T (1
Each of the next TT (1two space separated floating point numbersxx
T lines contains (2 ≤
x(2≤x≤100)
x ≤ 100) and vv (1<v≤100)
v (1 < v ≤ 100) \leq
. Both numbers have 55
5 digits after decimal. (2
(1 T \leq
\lt \leq x
Output 5
v \leq
for each case \times
Print the answer\leq 100)if
in a separate line. Your answer is considered correct
100) error does
its absolute or relative 10^4not) exceed10−610^{-6}
−6
10 . Formally, let your answer AAA
be ,
∣A−B∣
and the jury's answer be BB
B . Your answer is accepted if and only if ∣A−B∣max(1,B)
≤\leq
10−610^{-6}
−6
max(1,B) ≤ 10 .
\frac{\lvert
A-
B
\rvert}

BUET Inter University Programming Contest 2023 | Toph 10 of 24

Samples {\max(1,
B)}
Input Output
2 4.374718737669
2.50000 2.60000 10.637610774649
10.00000 100.00000

BUET Inter University Programming Contest 2023 | Toph 11 of 24

F. Chocolate
• BUET CSE FEST’23 has come to an end!!!! Chimatu Can’t stop crying as he already
started to miss the festive vibe so much. To make him happy again you need to buy
some chocolates for him. But yeah you are a well known miserable person, and so
that you want to spend as less money as you can.

Now comes the real problem. You need to buy nn

n chocolates.
You can buy 22
2 types of chocolates. Each type has a infinite amount of chocolates.
The first type chocolate has an initial pricepp
p, where the second type chocolate has an
initial price qq
q.
Each time one buys a chocolate of the first type, the price of this type gets decreased
by xx
x. Similarly, each time a second type chocolate is bought, the price of this type gets
decreased by yy
y.
Say p=9p
p = 9 andx=3x 99is
x = 3 for the first type of chocolate. Currently the price 9. After
= one chocolate
buying = the price decreases by 33
3 and now the new price is 66
6. After buying
9 chocolate
another 3 the price will again decrease by 33
3 and the new price will be 33
3.
You have to find the minimum cost to buy nn
n chocolates and make Chimatu happy!!!
[Note: It is guaranteed that the price of any chocolate will never be negative]

Input
The first line of the input contains an integer tt
t denoting the number of test cases.
The next line of each test case contains 5 space separated integers.

• nn
n- The amount of chocolates to be bought.
• pp
p- The initial price of first type chocolate
• qq
q - The initial price of second type chocolate
• xx
x- The amount of price reduces after buying each chocolate of first type
• yy
y - The amount of price reduces after buying each chocolate of second type

BUET Inter University Programming Contest 2023 | Toph 12 of 24

\le
Constraints
t
\le≤ t ≤ 105
11≤t≤1051
10^5
\le 6
11≤n≤1061
t ≤ n ≤ 10
\le
\le ≤ x ≤ p ≤ 107
11≤x≤p≤1071
n
10^5
\le
\le ≤ y ≤ q ≤ 107
11≤y≤q≤1071\le
x\le
10^6
y\le
p
q\le
Output
\le
10
10
^^ output should contain tt
The t lines. iiith line of output should contain the minimum cost
77 ii
for ith test case.

Samples
Input Output
1 220
5 100 50 5 3

BUET Inter University Programming Contest 2023 | Toph 13 of 24

G. LR
This task is simple. You will be given 22
2 positive integers LL
L and RR
R.
Find the number of positive even integers xx L≤x≤RL
x such that L ≤ x ≤ R.
\leq
x
Input
\leq
The first line of input contains an integer TT R number of test cases.
T denoting the

The only line of each test case contains two integers LL

L and RR
R.

Constraints

11≤T≤1001
≤ T ≤ 100
\le
11≤L≤R≤10001
T ≤ L ≤ R ≤ 1000
\leq
\le
L
Output
100
\leq
R
Output one integer, the answer to the problem.
\leq
1000
Samples
Input Output
1 1
1 2

BUET Inter University Programming Contest 2023 | Toph 14 of 24

H. Better Together!
There are NN
N cities and initially 00
0 roads between them. You are the Civil Engineer (but a
programmer from heart!) who is in charge of constructing roads between these cities.

The cities are numbered from00

0 toN−1N MM
N − 1. There are M types of road constructions
-
which can be performed among these k=1,
cities. For each k= kk k -th
1, 2, 3, … , M , the
kind of road construction is to 1 xx 2,x such
choose an integer 0≤x<N0
that 0 ≤ x < N and
construct a new two-way road connectingxxcity x and 3,…,Mk \le
(x+Ak)city mod
(x +N(x
Ak ) mod N .
Performing the kk = +CkC_k
k -th kind of road construction once costs Ck xtaka.
1, A_k)<
You can do these MM
M kinds of road constructions any number of times
2, \text{
N mod (possibly
} zero) in
3, N
any order. For example, if three kinds of road constructions are available, you can
choose to perform the first type of road construction …,twice, the second zero times,
and the third once. M
The people of these cities want to travel from one city to another city. You have to
determine whether it is possible to make all the cities connected together. If possible,
then determine the minimum total cost. Here, “connected” means, there exists at
least one path from each city to every other city.

Constraints:

•2 ≤ N ≤ 109
2≤N≤1092\le
≤ M ≤ 105
• N\le10^9
11≤M≤1051\le
M\le
•1
1≤Ak≤N−11\le
≤ Ak ≤ N − 1
10^5
≤ Ck ≤ 109
A_k\le
•1
1≤Ck≤1091\le
•N
C_k\le
All values in input are integers.
-
10^9
1
Input
Input is given from Standard Input in the following format:

N MA1M C1A2 C2⋮AM CMN\

M\
A 1 C1
\A2 C2
A_1\
⋮C_1\
A
\ M CM
A_2\
C_2\
\

BUET Inter University Programming Contest 2023 | Toph 15 of 24

\vdots\
Output
\
If it is possible to make all the cities connected, print the minimum total cost needed
A_M\
to do so.
C_M
If it is impossible to make all the cities connected, print −1−1
−1.

Samples
Input Output
4 2 11
2 3
3 5

If we first do the road construction of the first kind to connect cities00

0 and222, then do it
again to connect cities11
1 and33
3, and finally the road construction of the second kind to
connect cities 11
1 and00
0, all the cities will be connected together. The total cost incurred
here is 3+3+5=113+3+5=11
3 + 3 + 5 = 11 taka, which is the minimum possible.

Input Output
6 1 -1
3 4

There is no way to make all the cities connected, so we should print −1−1
−1.

BUET Inter University Programming Contest 2023 | Toph 16 of 24

I. Reassemble
There are NN
N posts in a line numbered from 11
1 toNN
N from left to right. Each postiii has a
distance did_i
di which describes how far it is from the base of operation. The more left you
1≤d1<d2<d3<…
go, the closer you get to the base. More formally, 1 ≤ d1 < d2 < d3 < … < dN .
<dN1\leq
iii has a troop ofiii soldiers. Now it is
Each post has a different number of soldiers. Postd_1
time for the drill and you need to shuffle the positions
< of the troops. You want the
troop ii
i to go the position PiP_i 1≤i≤N1\leq
Pi for all 1 ≤ i ≤ N . d_2
i\leq <
To keep the discipline, you will give N
the following commands one at a time. Choose two
d_3
distinct posts,iii andjj j where
(1≤i,j≤N)
(1 ≤ i, j ≤ N ), and swap the troops. All soldiers
<
currently stationed at postiii(1\leq jj j and all soldiers currently stationed at
will go to post
…
post jj i,j\leq
j will go to postii i. When ii < ijjto j , one soldier needs to walk
moving from post
∣di−dj∣|
∣di − dj ∣ unit of distance.
N)
d_N
d_i
You
- can give as many commands as you want until each troop is at its desired position
but
d_j|you want to do it such that the total distance crossed by all soldiers is as minimum
as possible. You also want to minimize the total number of commands after
minimizing total distance crossed.

Input
The first line of the input will contain an integer, T (1≤T≤100)T\
(1 ≤ T ≤ 100) which denotes the
number of test cases. (1\leq
T\leq
Each of the test cases starts with one integer N (1 ≤ N ≤ 106 ) describing the
N (1≤N≤106)N\
100)
number of posts. (1\leq
N\leq
The next line will containNN integersd1,
N space separated10^6) d1d2,
, d2d3,…,
, d3 , …dNd_1,\
, dN where did_i
di
7
d_2,\
denotes the distance of postiii from base.1≤di≤107,
1 ≤ di ≤ 10 di<di+1
, di < dfor
i+1 all
for1≤i<N1\leq
all 1 ≤ i <
N. d_i\leq d_3,
10^7,\ …,
The next line will contain NN
N more spaced_i P1, PP2,
separated \integers 1, PP3,…, PNP_1,\
2 , P3 , … , PN .
Troop currently stationed at post ii i should
< be stationedd_N P_2,\
atPiP_i
post Pi after all the
commands are given. 1≤Pi≤N
1 ≤ Pi ≤ and
N andall all
Pi are distinct1\leq
Pi are P_3,
, so PP
distinctfor
d_{i+1}\text{ P is a permutation of
length NN
N. P_i\leq all } …,
N\text{ and 1\leq \
It is guaranteed that the sum
all } of NN
N over all
i<test cases does not
P_N 106 .
exceed 10610^6
P_i\text{ are N
distinct}

BUET Inter University Programming Contest 2023 | Toph 17 of 24

Output
CCC and
For each test case output two integers QQQ in the first line, where
CC C is the
minimum distance crossed by all soldiers andQQ
Q is the minimum number of commands
needed to do that. Then outputQQ
Q more lines, each of them will contain two integers
(i =
i,jj(i≠j,
i,  1≤i,j≤N)i,j\
j, 1 ≤ i, j ≤ N ) which denotes a command. NOTE: Troop currently
(i\neq at post iii must be stationed at postPiP_i
stationed Pi after allQQ
Q commands are applied
j, chronological order. First you need to minimizeCC
in C , then minimizeQQQ. If there are
\multiple sets of commands of size QQ
Q so that the total distance crossed remainsCC C,
1\leq
print any of them.
i,j\leq
N)
Samples
Input Output
2 86 2
3 3 2
1 10 20 2 1
2 3 1 20 2
4 3 1
1 2 3 4 4 2
3 4 1 2

BUET Inter University Programming Contest 2023 | Toph 18 of 24

J. Eulers Peculiar Dream
ϕ(x)
After discovering the famous totient function ϕ(x) Euler got so fond of it that he
applied it to every number he could find on his\phi(x)
table. He played all day with this newly
discovered function. Then he went to sleep. He was dreaming about the function too.

In the dream, he found a very big number xx

x. Since he was playing with totient function
xxx and got a new number
he immediately applied totient function to ϕ(x)ϕ(x). But the
\phi(x)
number was still very large so he again applied totient to it and got another number
ϕ(ϕ(x)) which was still way too big. As a result, Euler got frustrated. He wondered
ϕ(ϕ(x))
\phi(\phi(x))
how many times he had to apply totient function before reaching111. Euler solved it in
the dream. Can you do it too?

y0=xy_0
Formally, let y0 =x
=
xn−1 ) where nn
n = ϕ(y
yn=ϕ(yn−1)y_n
and y n≥1n\ge
n is an integer and n ≥1
= 1
Find smallest nn
n such that yyn=1y_n
n =1
\phi(y_{n-1})
=
1 of a positive integer nn
Note: Euler totient function n is defined as the number of positive
integers ii
i less than or equal to nn gcd(n,i)=1gcd(n,i)
n such that gcd(n, i) = 1
=
1
Input
k(1 ≤ k ≤ 105 )
First line of input contains an integer k(1≤k≤105)k
( 1\le
Next line contains kk p1,p2,…
k prime numbers pk1 , p2 , … pk
pkp_1,
\lee
Next line contains kk
k integers ee1,e2,…
1 , e2 , p_2,
… k
10^5)
eke_1,e_2,…
6…
For each 11≤i≤k1\le
≤ i ≤ k , 22≤pi≤1062
≤ pi ≤ e_k10 p_k
i\le \le
It is guaranteed
k that p_i pip_i
each pi is pairwise distinct.
For each 1 ≤ i ≤ k , \le
1≤i≤k1\le ≤ ei ≤ 106
11≤ei≤1061
i\le 10^6
\le k
Then the kinput number e_iis calculated as x = ∏i=1 pei i
x=∏i=1kpieix
\le =\prod_{i
10^6 =
Output
1}
Print the smallest positive nn yyn=1y_n
n =1
n such that ^{k}
=
p_i^{e_i}
Since nn
n can be very large, output it modulo 1 998244353998244353
998244353

BUET Inter University Programming Contest 2023 | Toph 19 of 24

Samples
Input Output
2 2
3 2
1 1

Input Output
1 4
11
1

BUET Inter University Programming Contest 2023 | Toph 20 of 24

K. Cold Rainy Night in Stoke
NNN points in 2D-coordinate plane in your dream.
Night is ending. You have just got
Wait! Things were going well with the points. Suddenly, a circle appeared, which is
centered at coordinate (0, 0) and has a radius of RR
R. Your mind is telling you to create a
convex polygon, whose0)vertices are subset of those
NNN points. This convex polygon
must enclose the circle (0,0)
completely. That is, no point of the circle (including the points
on its boundary) is strictly outside the polygon. The polygon may touch the circle.

This is not enough. You have to find the polygon with smallest area. Output the value
of the smallest area×2\times
×2. If it is impossible to construct such a polygon, output should
be −1-1
−1. 2

Let’s just solve this problem before the night ends.

Input
First line of the input will have an integerTT(1 ≤ T ≤ 100), denoting the number of
T(1≤T≤100)
testcases. Each testcase is independent. (1
\le
TNN(1≤N≤500)
First line of each testcase will have an integer N (1 ≤ N ≤ 500), denoting the
number of points you have got. \le (1
\le
100)xix_i
Line ii
i of the nextNNN lines will have two integers yiy_i
N xi and yi (−104 ≤ xi , yi ≤ 104 )
(−104≤xi,yi≤104)
denoting the abscissa and ordinate ii (-10^4
i-th point respectively,
\le for ii=1,
= 1, 2, … , N .
500) \le 2,…,Ni=1,
4
Last line of each testcase will have an integerRR R(1≤R≤104)
(1 ≤ R x_i,
≤ 10 2, ), denoting the radius
of the circle. (1\le y_i \dots,
R \le N
Sum of NNN over all testcases will not exceed 500500
500.\le
10^4)
10^4)
Output
Print a separate line for each testcase. Lineiii of the output should have the output for
ii
i-th testcase. Output of the iii-th testcase is the value of2×A2
2 × A, whereAA
A is the area of
\times
the smallest possible convex polygon. If there is no possible convex polygon, output is
−1-1
−1. A

BUET Inter University Programming Contest 2023 | Toph 21 of 24

Samples
Input Output
2 144
6 -1
-6 0
-4 4
0 6
0 -6
2 2
6 0
4
1
5 5
1

Following figures show the input of 1st testcase and the convex polygon with smallest
area. Here the area is 7272
72.

BUET Inter University Programming Contest 2023 | Toph 22 of 24

L. Gardening
You are given a tree withNN
N vertices. Here, a tree is an undirected graph in which any
two vertices are connected by exactly one simple path, or equivalently a connected
acyclic undirected graph. A tree withNN
N vertices, contains exactlyN−1N
N − 1 undirected
edges. -
1
You have to processQQ
Q queries. In each of the query, you will be given 3 positive
integers RR
R, UU
U and VV
V . You have to perform the following operations on your tree —
• Add an edge between UU
U and VV
V.
• Remove an edge such that the resulting graph is still a tree. You can also remove
the newly added edge.

• Minimize the sum of distance of every vertex from the vertex RR

R. Formally , let did_i
di
denote the shortest distance from vertexRR ii i. You have to minimize
R to vertex
∑1≤i≤ndi\sum_{1\le
∑ 1≤i≤n di
i\le
• Print the Minimized Sum
n}
^{}
Note that, Each query is independent which means operations in one query does not
d_i
affect the other queries.

Input
NN(2≤N≤3×105)
The first line of the input will contain an integer, N (2 ≤ N ≤ 3 × 105 ) which
denotes the number of vertices of the tree. (2
\leq
Each of the nextN−1N
N − 1 lines will contain222 space-separated
N integersuiu_i viv_i
ui and (1≤ui,vi≤N)
vi (1 ≤
-
ui , vi ≤ N ), indicating an edge between verticesuiu_i vi . It is guaranteed (1
i andviv_i
u\leq that the
given edges form1a tree. 3 \leq
\times u_i,
The next line will contain an integer QQ ≤ Q ≤ 3 × 105 ), the number of queries.
(1≤Q≤3×105)
Q (1 v_i
10^5)
(1\leq \leq
Finally, each of the next QQ
Q line will contain
Q\leq33
3 integers RiR_i
Ri ,UiU_i
Ui and ViV_i
Vi(1≤Ri,Ui,Vi≤N)
(1 ≤ Ri , Ui , Vi ≤
N)
N ) — representing each query. 3\times (1
10 \leq
^ R_i,
Output
5) U_i,
Print the answer for each query in separate lines. V_i

BUET Inter University Programming Contest 2023 | Toph 23 of 24

Samples \leq
N)
Input Output
5 9
2 1 8
3 1 9
4 3 6
5 1
4
4 2 1
2 1 2
4 2 1
4 4 1

Input Output
6 9
1 2 9
2 3
3 4
4 6
1 5
2
1 5 6
1 5 4

Input Output
10 27
2 1 23
3 2
4 3
5 3
6 4
7 2
8 4
9 8
10 7
2
1 10 4
9 1 9

BUET Inter University Programming Contest 2023 | Toph 24 of 24