TCPC Tunisian Collegiate Programming Contest 2022
A. Mood
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Hazem is a really clever boy. He goes to school every day and always gets high marks in all of the quizzes he takes. Today he is not in a good mood to study, so he wants to buy and drink his favorite drink to feel better.

He has only $$$x$$$ pounds, and the drink costs $$$y$$$ pounds. Help him know what the minimum number of pounds he needs to borrow from his father so that he can buy the drink.

Input

The first line contains a single integer $$$t$$$ $$$(1\leq t \leq 10^{5})-$$$ the number of testcases.

The only line of each test case contains two integers $$$x$$$ and $$$y$$$ $$$(1\leq x, y \leq 10^{5})-$$$ the number of pounds Hazem has and the cost of the drink, respectively.

Output

For each test case, print one integer $$$-$$$ the minimum number of pounds he needs to borrow from his father so that he can buy the drink.

Example
Input
3
7 10
2 4
5 3
Output
3
2
0

B. Hungry
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Hendy is hungry and wants to eat asandwich. He has two options:

  • Go to the shop in $$$x$$$ minutes, then wait in the queue until he gets his order.
  • Order his food by delivery, but the shop has a rule: the shop will serve the first $$$m$$$ people in the queue, then deliver the order in $$$y$$$ minutes.

Currently, there are $$$n$$$ customers in the queue, and it takes $$$a_{i}$$$ $$$(1\leq i \leq n)$$$ minutes to serve the $$$i_{th}$$$ customer (the shop serves only one customer at once).

Assume that the shop won't take time to prepare the food and there won't be any new customers after the current $$$n$$$ customers.

You are given $$$q$$$ queries. For each query, you are given $$$x$$$,$$$y$$$ ,and $$$m$$$. For each query, you have to find the minimum time required for Hendy to get his food.

Input

The first line contains a single integer $$$n$$$ $$$(1 \leq n \leq 10^{5})- $$$the number of customers in the queue.

The second line contains $$$n$$$ integers $$$a_{1},a_{2},...,a_{n}-$$$ time to serve the $$$i_{th}$$$ customer.

The third line contains $$$q$$$ $$$(1 \leq q \leq 10^{5})- $$$the number of queries.

The next $$$q$$$ lines contain three integers $$$x$$$, $$$y$$$ $$$(1\leq x,y \leq 10^{9})$$$ and $$$m$$$ $$$(1 \leq m \leq n)- $$$the time to reach the shop, time to deliver the order, and the number of customers the shop will serve before delivering the order, respectively.

Output

For each query , print a single line that is the answer to the problem.

Example
Input
5
1 2 1 3 4
5
3 4 3
5 10 2
1 3 3
10 4 2
15 10 5
Output
8
11
7
7
15

C. Ice Coffee
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Ali loves ice coffee, so Ahmad offers him ice coffee if he can solve this problem. Ali is not good at problem solving, so he asked for your help to solve the problem and get the Ice Coffee.

Given two arrays A and B the goal is to make array A equal to B.

There are two types of operations :

  • $$$A_{i} := next(A_{i})$$$
  • $$$B_{i} := next(B_{i})$$$

$$$next(x)$$$ = the greatest divisor of the number $$$x$$$, excluding $$$x$$$ itself.

For example, $$$next(12) = 6$$$, $$$next(18) = 9$$$.

Given two arrays print the minimum number of operations (possibly zero) to make arrays $$$A$$$ and $$$B$$$ equal.

Two arrays $$$A$$$ and $$$B$$$ of length $$$n$$$ are considered equal if $$$A_{i} = B_{i}$$$ for all $$$i$$$ $$$(1 \le i \le n)$$$

Input

The first line contains a single integer $$$t$$$ $$$(1 \le t \le 10^4)$$$ - The number of test cases.

Each test case has 3 lines :

The first line contains a single integer $$$n$$$ $$$(1 \le n \le 10^5)$$$ - The length of the two arrays.

The second line contains $$$n$$$ integers $$$A_{1}, A_{2}...,A_{n}$$$ $$$(1 \le A_{i} \le 10^7)$$$ - elements of the array $$$A$$$.

The third line contains $$$n$$$ integers $$$B_{1}, B_{2}...,B_{n}$$$ $$$(1 \le B_{i} \le 10^7)$$$ - elements of the array $$$B$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2.10^5$$$.

Output

For each test case, print one integer - The minimum number of operations (possibly zero) to make arrays $$$A$$$ and $$$B$$$ equal.

Example
Input
3
4
4 5 12 1
8 3 9 2
2
5 4
10 6
1
2
8
Output
7
5
2

D. Beautiful decrease
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Meshmesh started learning about operations on sub-arrays, so his mentor gave him a problem to solve using what he has learned.

Given an array $$$A$$$ with size $$$n$$$ and $$$Q$$$ queries. In each query, Meshmesh will perform at most $$$k$$$ beautiful decreases.

In one beautiful decrease, You can decrease each element in one sub-array by 1 such that the sum of the array is minimized, and each element in the chosen sub-array must be greater than 0.

But his mentor asks him to update the array after doing the beautiful at the $$$i_{th}$$$ query and print the sum of the new array.

Note: the decreases are permanent, they change the array.

For example: given $$$n=8$$$, $$$A={3,5,4,3,3,4,1,5}$$$, $$$Q=1$$$; and first $$$k=2$$$, so the minimum sum will equal to $$$14$$$ and $$$A$$$ will be $$${1,3,2,1,1,2,0,4}$$$.

Meshmesh thinks that the problem is too difficult form him to solve and asks for your help. Can you help him ?

Input

The first line contains two integers $$$n$$$ and $$$Q$$$ $$$(1\leq n, Q \leq 10^{5})-$$$ array size and the number of questions that Meshmesh will answer.

The next line contains $$$n$$$ integers $$$A_{1}, A_{2},...A_{n}$$$ $$$(1\leq A_{i} \leq 10^{9})- $$$the given array elements.

Each of the next $$$Q$$$ lines contains $$$k_{i}$$$ $$$(1\leq k_{i} \leq 10^{5})- $$$ the number of beautiful decreases Meshmesh can perform in the array.

Output

$$$Q$$$ lines, each line contains the summation of the array after beautiful decreases.

Example
Input
8 5
3 5 4 3 3 2 1 5
2
1
2
1
1
Output
12
7
4
3
2

E. The Detective Game
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

One of the cool activities that the ACPC contestants do in ACPC is playing The Detective Game, a game where they apply their problem-solving, detective, critical thinking, attention to detail, and teamwork skills.

The game consists of $$$n$$$ players, one or more of them has the role of the doctor. In each round, the players discuss who they suspect to be the doctor, and a player is selected to be on trial, meaning that the other players will vote if they think that the selected player is a doctor or not.

If strictly more than $$$50\%$$$ of the $$$n$$$ players voted to eliminate a player from this round, the player will be eliminated; otherwise, the round will end disappointedly with no change.

You are given each player's suspect list, which is the list of other players who they think that they are doctors. You want to calculate for each player independently if they are selected to be on trial in the current round, will they be eliminated or not.

Your task is to print all the players, in increasing order, who will be eliminated if they are selected on trial this round.

Input

The input starts with an integer $$$T$$$, the number of test cases. Then $$$T$$$ test cases follow.

Each test case starts with a single integer $$$n$$$ $$$(2 \leq n \leq 10^{5})-$$$the number of players.

Then $$$n$$$ lines follow $$$-$$$ the $$$i_{th}$$$ line represents the $$$i_{th}$$$ players suspect list.

Each line starts with an integer $$$k_{i}$$$ $$$(0\leq k_{i} \leq)$$$, the number of players in his list, then $$$k_{i}$$$ distinct integers follow, each number $$$a_{ij}$$$ in the list $$$(1 \leq a_{ij} \leq n, a_{ij} \ne i)$$$ means that player $$$i$$$ will vote against player $$$a_{ij}$$$ if he was on trial.

It's guaranteed that the summation of all $$$n$$$ and $$$k_{i}$$$ will not exceed $$$4 \cdot 10^{5}$$$ in all test cases.

Output

For each test case, print an integer $$$m$$$ $$$(0\leq m \leq n)-$$$ the number of players who could be eliminated if they are selected on trial this round.

Then print $$$m$$$ integers in increasing order, $$$b_{i}$$$ $$$(1\leq b_{i} \leq n)$$$ representing the players who will be eliminated if they are selected on trial.

Example
Input
1
4
3 2 3 4
1 1
2 1 2
1 1
Output
1
1

F. Distinct
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a program that consists of $$$n$$$ instructions. Initially, a single variable $$$x$$$ is assigned to $$$1$$$.

Afterwards, the instructions are of two types:

  • divide $$$x$$$ by $$$2$$$ ($$$x = \lfloor{x/2}\rfloor$$$, integer division).
  • multiply $$$x$$$ by $$$2$$$.

You are given $$$m$$$ queries of the following format:

  • query $$$l$$$ $$$r$$$ $$$-$$$ how many distinct values is $$$x$$$ assigned to if all the instructions between the $$$l_{th}$$$ one and the $$$r_{th}$$$ one inclusive are executed without changing the order ?
Input

The first line contains a single integer $$$t$$$ $$$(1\leq t \leq 1000)- $$$the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$q$$$ $$$(1\leq n,q \leq 10^{6})- $$$the number of instructions in the program and the number of queries.

The second line of each testcase contains a program $$$-$$$ a string of $$$n$$$ characters: each character is either '$$$*$$$' or '$$$/$$$' $$$-$$$ multiply and divide instruction, respectively.

Each of the next $$$q$$$ lines contains two integers $$$l$$$ and $$$r$$$ $$$(1\leq l \leq r \leq n)-$$$ the description of the query.

The sum of $$$n$$$ over all test cases doesn't exceed $$$10^{6}$$$. The sum of $$$q$$$ over all test cases doesn't exceed $$$10^{6}$$$.

Output

For each test case, print $$$q$$$ integers $$$-$$$ for each query $$$l$$$,$$$r$$$, print the number of distinct values variable $$$x$$$ is assigned to if all the instructions between the $$$l_{th}$$$ one and the $$$r_{th}$$$ one inclusive are executed without changing the order and $$$x$$$ always starts with $$$1$$$.

Example
Input
2
12 5
*/**///*/*//
1 4
2 7
6 10
1 12
4 8
5 3
*//**
1 3
2 5
2 4
Output
3
2
2
4
3
3
2
2

G. String Rotation
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

After studying strings in his college, Beshoy wants to create a problem on strings for you.

Given two strings $$$s$$$ and $$$t$$$ of length $$$n$$$ consisting of lowercase English letters, and an integer $$$x$$$.

You are allowed in one operation to change any character in the string $$$s$$$ to any character you want.

Your task is to count the minimum number of operations needed to make string $$$s$$$ equal to string $$$t$$$ after rotating $$$s$$$ exactly $$$x$$$ times to the right.

One cyclic shift to the right is such a transformation that the string $$$s=[s_{1},s_{2},...,s_{n}]$$$ becomes equal to the string $$$s=[s_{n},s_{1},s_{2},...,s_{n-1}]$$$.

Input

The first line contains two integers $$$n$$$ and $$$x$$$ $$$(1\leq n\leq 10^{5}, 1\leq x \leq 10^{9})$$$.

The second line contains string $$$s$$$ of length $$$n$$$.

The third line contains string $$$t$$$ of length $$$n$$$.

Output

Print one integer $$$-$$$ the minimum number of operations needed to make string $$$s$$$ equal to string $$$t$$$ after rotating $$$s$$$ exactly $$$x$$$ times to the right.

Example
Input
5 2
abcgh
ahcbg
Output
3

H. Cookies
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Donia's sister baked some cookies, and she $$$-$$$ for some reason $$$-$$$ will not let her eat them. Some of the cookies were large, and others were small. Donia wants to eat as many large cookies as she can but without making her sister notice.

Donia's sister will not notice if at least $$$m$$$ cookies haven't been eaten.

Help Donia and tell her the maximum number of large cookies she can eat without making her sister notice.

Input

The first line contains $$$T$$$ $$$(1 \leq T \leq 10^{5})-$$$ the number of test cases.

The only line of each test case contains the integers $$$n$$$, $$$m$$$, $$$a$$$ $$$(1\leq m,a \leq n \leq 10^{12})- $$$the number of cookies Donia's sister baked and the minimum number of cookies Donia has to leave, the number of large cookies.

Output

For each test case, output one integer $$$-$$$ the maximum number of large cookies Donia can eat.

Example
Input
3
5 2 1
5 2 2
5 5 5
Output
1
2
0
Note

In the first test, Donia has to leave at least $$$2$$$ cookies, and there is only $$$1$$$ large cookie, so she will eat it and leave $$$4$$$ cookies.

I. Omar and Trees
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

When Omar was at school, his teacher gave him a challenge, and Omar accepted it.

The teacher gave Omar a tree of $$$n$$$ nodes (node $$$1$$$ is the root). The $$$i_{th}$$$ node has a value $$$a_{i}$$$.

Then the teacher asked Omar $$$q$$$ queries of two types:

  • Update the value in every node in the subtree rooted with $$$u$$$ to $$$val$$$ ($$$u$$$ included).
  • Determine if the sum of all nodes in the subtree with root $$$u$$$ can be represented as the sum of two prime numbers or not ($$$u$$$ included).

Omar asks for your help in this challenge.

Input

The first line contains one integer $$$n$$$ $$$(1 \leq n \leq 10^{5})$$$.

The second line contains $$$n$$$ integers $$$(1\leq a_{i} \leq 10^{5})- $$$the value of each node.

For each $$$n-1$$$ lines, it contains two integers $$$u$$$ and $$$v$$$ $$$(1\leq u,v \leq n, u\ne v)-$$$ indices of nodes connected by an edge.

Then the number of queries $$$q$$$ $$$(1\leq q \leq 10^{5})$$$.

Each query format is one of the following:

  • $$$1$$$ $$$u$$$ $$$val$$$: Update the value in every node in the subtree rooted with $$$u$$$ to $$$val$$$ $$$(1\leq val \leq 10^{5})$$$.
  • $$$2$$$ $$$u$$$: Determine if the sum of all nodes in the subtree with root $$$u$$$ can be represented as the sum of two prime numbers or not.
Output

For each query of the second type, print "$$$YES$$$" without quotes if the sum of all nodes in the subtree with root $$$u$$$ can be represented as the sum of two prime numbers or not, "$$$NO$$$" without quotes otherwise.

Example
Input
9
3 5 2 7 10 6 1 4 3
1 2
2 3
1 4
4 5
5 6
4 7
7 8
7 9
6
2 7
2 2
1 7 10
2 7
1 7 9
2 7
Output
YES
YES
YES
NO

J. Hide and Seek
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Gamal and Amr have just returned from school after a long day. They were bored, so they went to the park and decided to play a hide and seek game.

The park contains $$$n$$$ trees of different heights. The $$$i_{th}$$$ tree has height $$$h_{i}$$$. Amr will start hiding behind a tree, and Gamal will start looking for him.

Gamal will only catch Amr if Amr hid behind a tree that is strictly shorter than him.

You know Amr's height, which is equal to $$$x$$$, and the height of each tree in the park.

For every tree, your task is to determine if Amr will be caught if he hid behind it or not.

Input

The first line contains a single integer $$$t$$$ $$$(1 \leq t \leq 10^{3})- $$$the number of testcases.

The first line of a test case contains integers $$$n$$$ and $$$x$$$ $$$(1\leq n,x \leq 10^{5})- $$$the number of trees in the park and Amr's height, respectively.

The second line of a test case contains $$$n$$$ integers $$$h_{1},h_{2},...,h_{n}$$$ $$$(1\leq h_{i} \leq 10^{5})-$$$ the heights of the trees in the park.

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

Output

For each test case, print $$$n$$$ integers $$$a_{1},a_{2},...,a_{n}$$$, where $$$a_{i}=1$$$ if Amr will be caught when he hid behind the $$$i_{th}$$$ tree, otherwise $$$a_{i}=0$$$.

Example
Input
3
5 3
1 3 1 10 2
3 2
1 1 1
2 2
2 2
Output
1 0 1 0 1 
1 1 1 
0 0

K. Wrong digits
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Ghadeer is a hard-working girl. After finishing university, she decided to apply for a job. The manager gave her a problem to solve.

You are given two digital numbers of length $$$n$$$ and you have to make them equal by using the following operations.

  • Erase one dash of any digit.
  • Add one dash to any digit.

The first operation can only be used at most $$$x$$$ times. The second operation can only be used at most $$$y$$$ times.

Example: To convert from $$$5$$$ to $$$4$$$, you have to use $$$2$$$ operations of the first type and 1 operation of the second type.

You are asked to determine if she can make the two numbers equal.

The operations can be applied to any of the two numbers. Note: After doing the operations, the resulting number should be a valid digital number

Input

The first line contains an integer $$$T$$$ $$$(1 \leq T \leq 100)-$$$ the number of testcases.

Each test case has $$$3$$$ lines:

The first line contains $$$n$$$, $$$x$$$, $$$y$$$ $$$(1 \leq n,x,y \leq 100)-$$$ the number of digits of the two numbers, number of the first operation, number of second operation, respectively.

The second line contains $$$s$$$ $$$(1 \leq s \leq 10^{100})-$$$ the first number.

The third line contains $$$t$$$ $$$(1 \leq t \leq 10^{100})-$$$ the second number.

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

Output

For each test case , print "$$$YES$$$" if she can , otherwise print "$$$NO$$$".

Example
Input
4
3 2 3
221
547
5 10 15
12345
54321
2 1 2
23
17
1 1 1
1
1
Output
NO
YES
NO
YES

L. Black and White Tree
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a tree of $$$n$$$ nodes rooted at node $$$1$$$, and every node is colored either black or white.

Given $$$q$$$ queries consisting of a node $$$u$$$, your task is to count how many nodes $$$v$$$ exist in the subtree of node $$$u$$$ such that in the path from $$$u$$$ to $$$v$$$, the number of black nodes equals the number of white nodes, including $$$u$$$ and $$$v$$$.

Input

The first line contains two integers $$$n$$$ and $$$q$$$ $$$(1\leq n \leq 10^{5}, 1 \leq q \leq 10^{5})-$$$ the number of nodes in the tree and the number of queries, respectively.

The second line contains $$$n$$$ integers $$$c_{1},c_{2},...,c_{n}$$$ $$$(0\leq c_{i} \leq 1)$$$, where $$$c_{i}=0$$$ means that the $$$i_{th}$$$ node is white and $$$c_{i}=1$$$ means that the $$$i_{th}$$$ node is black.

Each of the next $$$n-1$$$ lines describes an edge of the tree. The $$$i_{th}$$$ edge is denoted by two integers $$$u_{i}$$$ and $$$v_{i}$$$, the labels of nodes it connects $$$(1\leq u{i},v_{i} \leq n, u_{i} \ne v_{i})$$$.

It is guaranteed that the given edges form a tree.

The next $$$q$$$ lines contain the queries. The $$$j_{th}$$$ line contains one integer $$$u$$$ $$$(1\leq u \leq n)$$$.

Output

Print $$$q$$$ integers $$$-$$$ the answers to the queries in the order they appear in the input.

Example
Input
3 3
1 0 1
1 2
3 2
1
2
3
Output
1
1
0

M. Delivery
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Mazen challenged his brother Amir to solve this problem. Mazen loves consecutive ranges.

Given a number $$$x$$$, is there a range from $$$l$$$ to $$$r$$$ (inclusive) such that $$$\sum_{i= l}^{r} i = x$$$ where $$$(r \lt x)$$$.

If a range exists, output the $$$l$$$ and $$$r$$$ of such a range, otherwise output -1.

Input

The first line contains a single integer $$$t$$$ $$$(1 \le t \le 10^3)$$$ - the number of test cases.

The only line of each test case contains one integer $$$x$$$ $$$(1 \le x \le 2.10^9)$$$

Output

For each test case, If there is no valid range, output -1.

Otherwise, print 2 integers $$$l,r$$$ $$$(1 \le l \lt r \lt x)$$$ - indicates the range. If there are multiple solutions, output any.

Example
Input
3
4
9
88
Output
-1
4 5
3 13

N. How many rectangles?
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Doha and Takoo love geometry. Doha wants to give a geometry problem to Takoo and challenges her to solve it.

There are $$$n$$$ rectangles. Doha gives Takoo two coordinate points for each rectangle. The first one is the lower left point $$$(x_{1},y_{1})$$$ and the second one is the upper right point $$$(x_{2},y_{2})$$$. Takoo will record all the coordinates' points, and Doha will ask her $$$Q$$$ queries. In each query, Doha gives her the upper right points of a rectangle that start from the origin. She asks Takoo to count the number of rectangles totally included in this boundary.

For example, given:

  • First rectangle $$$x_{1}$$$,$$$y_{1}$$$ $$$(1,2)$$$ and $$$x_{2}$$$,$$$y_{2}$$$ $$$(7,6)$$$.
  • Second rectangle $$$x_{1}$$$,$$$y_{1}$$$ $$$(7,0)$$$ and $$$x_{2}$$$,$$$y_{2}$$$ $$$(10,3)$$$.
  • Boundary $$$x$$$,$$$y$$$ $$$(8,10)$$$
  • There is one rectangle in this boundary.
Input

The first line of input contains $$$n$$$ $$$(1 \leq n \leq 10^{5})$$$, where $$$n$$$ is the number of rectangles.

The following $$$n$$$ lines contain $$$2D$$$ coordinate points for each rectangle $$$(x_{1}$$$,$$$y_{1})$$$, $$$(x_{2}$$$,$$$y_{2})$$$ $$$(0\leq x_{1} \lt x_{2} \leq 10^{9})$$$ $$$(0\leq y_{1} \lt y_{2} \leq 10^{9})$$$.

The third line of input contains $$$Q$$$ $$$(1 \leq Q \leq 10^{5})$$$ where $$$Q$$$ is the number of queries Doha asks to Taboo.

Each of the next $$$Q$$$ lines contains $$$x$$$ and $$$y$$$ $$$(0\leq x,y \leq 10^{9})$$$ where $$$x$$$, $$$y$$$ are the coordinates of the upper right corner of the query rectangle that starts from the origin.

Output

$$$Q$$$ lines, each line contains the number of rectangles in this boundary.

Example
Input
5
2 3 3 4
4 7 5 8
1 10 4 15
2 5 5 8
4 10 7 12
7
7 5
15 20
6 10
7 11
4 10
3 9
6 8
Output
1
5
3
3
1
1
3