Zaglol Contest - FCDS level 2 contest 2026
A. Zaglol welcoming
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Welcome to FCDS contest. You are given a string $$$s$$$. Your task is to print $$$FCDS$$$ regardless of the input.

Input

The first line contains a string $$$s$$$.

Output

Print $$$FCDS$$$

Example
Input
baraa
Output
FCDS

B. El GCD haywady Ashraf fe 7eta tanya
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Ashraf would love to tell you an interesting long story about some interesting topics but he is busy so here is the problem statement directly ^_^.

Given an integer $$$n$$$ determine if there are two integers $$$x$$$ and $$$y$$$ $$$(1 \lt x,y)$$$ such that $$$x+y=n$$$ and $$$gcd(x,y) \gt 1$$$.

Input

The first line of input consists of one integer $$$T$$$ $$$(1\leq{T}\leq{10})$$$ the number of test cases.

Each test case consists of an intger $$$n$$$ $$$(1\leq{n}\leq{10^{12}})$$$.

Output

Print $$$YES$$$ if there are valid $$$x$$$ and $$$y$$$ that their sum equal to $$$n$$$ and their $$$gcd$$$ greater than $$$1$$$ otherwise print $$$NO$$$.

Example
Input
3
14
5
35
Output
YES
NO
YES
Note

For the third testcase $$$35$$$ one valid answer is pair $$$(5, 30)$$$.

C. Fady: Ya baraaaa el mat3am feeeen
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

One day, "Soo2 Taghezya" team was at ACPC 2025. Fady got lost because the hotel was very large, so he asked Baraa for directions to return to his team. Baraa decided to help him by giving him a problem.

He gave him an odd integer $$$N$$$ and $$$N$$$ integers $$$H_1,H_2,\dots,H_N$$$, and also $$$M$$$ integers $$$W_1,W_2,\dots,W_M$$$.

Fady must choose exactly one integer $$$W_k$$$ and add it to the multiset $$${H_1,H_2,\dots,H_N}$$$, obtaining $$$N+1$$$ integers. Then, he must partition these $$$N+1$$$ integers into exactly $$$(N+1)/2$$$ disjoint unordered pairs $$$(x_i,y_i)$$$.

The cost of a pair $$$(x_i,y_i)$$$ is $$$|x_i-y_i|$$$, and the total cost is $$$\sum_{i=1}^{(N+1)/2}|x_i-y_i|$$$. Help Fady choose $$$W_k$$$ and form the pairs so that the total cost is minimized.

Input

The first line contains two integers $$$N$$$ and $$$M$$$ ($$$1 \le N, M \le 2 \times 10^5$$$).

The second line contains $$$N$$$ integers $$$H_1, H_2, \dots, H_N$$$ ($$$1 \le H_i \le 10^9$$$).

The third line contains $$$M$$$ integers $$$W_1, W_2, \dots, W_M$$$ ($$$1 \le W_i \le 10^9$$$).

Output

Print a single integer, the minimum possible total cost.

Example
Input
3 2
1 5 10
6 12
Output
6

D. Ashraf's Town
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Ashraf and his two teammates want to live in a weird town that has $$$n$$$ houses connected by undirected roads such that any house can go to any other house passing through roads and every two houses have a unique path between them.

Ashraf had an argument with his teammates, so he wants to live as far from them as possible, so he wants to know which house he can choose for himself and the two houses he can choose for his two teammates, such that the sum of the number of roads from them to his house is maximum and the three houses are $$$distinct$$$.

Example of the first test case
Input

The first line of input consists of one integer $$$n$$$ $$$(3\leq{n}\leq{2\cdot10^5})$$$ , the number of houses in the town.

Then $$$n-1$$$ lines follow, the $$$i$$$-th line containing two integers $$$a_i$$$ , $$$b_i$$$ $$$(1\leq{a_i,b_i}\leq{n}$$$, $$$a_i\neq{b_i})$$$ — the two houses that the $$$i$$$-th road connect.

Output

In the first line print one integer, the number of the house that Ashraf will choose.

In the second line print two integers, the houses of the two teammates.

If there are multiple solutions, print any.

Examples
Input
3
1 2
1 3
Output
3
2 1
Input
4
1 2
1 3
1 4
Output
3
2 4
Note

In the first example, Ashraf will reside in house number $$$3$$$ and his two teammates will reside in house $$$1$$$ and $$$2$$$.

So Ashraf's distance to $$$house$$$ $$$1$$$ is equal to $$$1$$$

and Ashraf's distance to $$$house$$$ $$$2$$$ is equal to $$$2$$$

so the sum of distances $$$1+2= 3$$$ which is the maximum they can achieve.

There are multiple answers like Ashraf can reside in house 2 and the two teammates in houses 1 and 3 you can print any which maximizes the sum of the two distances

E. Baby Baraa playing with LEGO
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

One day, Baraa was in Saudi Arabia. He went to his favourite store that sells games.

He saw many games there but he chose his favourite type of games LEGO.

When he returned to home, he started to play with the new LEGO game but suddenly he found that some piece is lost.

Baby Baraa started to cry and asked his mother to find it but she couldn't I hope you are sad for Baby Baraa.

So here is your problem, You are given an array $$$a$$$ of $$$n$$$ integers $$$a_1,a_2,a_3,…,a_n$$$ each $$$a_i$$$ is a piece of LEGO of type $$$a_i$$$. There are $$$n$$$ types of LEGO pieces.

You have to answer $$$q$$$ independent queries, each consisting of two integers $$$l$$$ and $$$r$$$. Consider the subarray $$$a[l:r] = [a_l,a_{l+1},…,a_r]$$$.

The answer to the query is any type of LEGO piece that is not found in this subarray.

Can you help Baby Baraa to find any missing piece to make him stop crying ?.

Input

The first line contains two integers $$$n$$$ and $$$q$$$ $$$(1≤n,q≤2⋅10^5)$$$ — the length of the array $$$a$$$ and the number of queries.

The next line contains $$$n$$$ integers $$$a_1,a_2,…,a_n$$$ $$$(1≤a_i≤n)$$$ — the pieces of LEGO.

The $$$i$$$-th of the next $$$q$$$ lines contains two integers $$$l_i$$$ and $$$r_i$$$ $$$(1≤l_i≤r_i≤n)$$$ — the description of the $$$i$$$-th query.

It is garaunteed that there is an answer for each query.

Output

For each query, output a single integer — the type of any LEGO piece that is not found in the subarray from $$$l_i$$$ to $$$r_i$$$.

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

For the first query the elements in the subarray is $$$[1,2,3]$$$ and the missing types of LEGO pieces are $$$4$$$ and $$$5$$$ so you can output anyone of them.

F. El mask mesh hena
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Given an array $$$a$$$ of length $$$n$$$.

There is a set $$$S$$$ where it contains the bitwise-OR of all subarrays of the array $$$a$$$.

Your task is to print the bitwise-AND of all numbers in the set $$$S$$$.

Input

The first line contains an integer $$$n (1 \le n \le 200000)$$$ — the length of the array.

The second line contains $$$n$$$ integers $$$a_1, a_2, ...., a_n$$$ $$$(1 \le a_i \le 10^9)$$$

Output

Print a single integer, the bitwise-AND of the bitwise-OR of all subarrays.

Example
Input
2
1 4
Output
0
Note

array $$$a = [1, 4], S = [1, 4, 5]$$$, bitwise-AND of $$$S$$$ = 0.

There are 3 subarrays of $$$a$$$ which are $$$[1], [4], [1, 4]$$$; the bitwise-OR of each one respectively is $$$1, 4, 5$$$.

G. Zeyad's Symmetric Functions
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

This problem is about the function $$$\textbf{f(x)=1/x}$$$. Given $$$l$$$ and $$$r (-10^{18} \le l \le r \le 10^{18})$$$. For each $$$\textbf{non-zero integer}$$$ $$$x_i (l \le x_i \le r)(x \neq 0)$$$,consider the triangle formed by:

1) The $$$X$$$-Axis

2) The $$$Y$$$-Axis

3) The tangent line to the curve $$$f(x) = 1/x$$$ at the point $$$(x_i , f(x_i))$$$

Find the sum of the areas of all such triangles.

Input

The only line of input contains two integers $$$l$$$ and $$$r (-10^{18} \le l \le r \le 10^{18})$$$.

(It's guaranteed that at least one of them doesn't equal 0)

Output

Print a single integer — the sum of the areas of the triangles.

Example
Input
1 1
Output
2
Note

The answer of the testcase, as in the image, is $$$(1/2) * 2 * 2 = 2$$$.

H. Fady mesh fady
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Fady was playing "Skrew sa7b sa7bo" was his friends at the college. Suddenly, Came up to his mind an interesting Math problem. You are given an integer $$$N$$$ and $$$N$$$ positive integers $$$A_1, A_2, ..., A_N$$$. You need to choose $$$N$$$ positive integers $$$B_1, B_2, ..., B_N$$$ such that for all $$$(i \lt j)$$$: $$$A_i B_i = A_j B_j$$$ Among all such choices. Can you help Fady find the minimum possible value of: $$$B_1 + B_2 + ... + B_N$$$? Print the minimum value.

Input

The first line contains an integer $$$N$$$ $$$(1 \le N \le 2 * 10^5)$$$. The second line contains $$$N$$$ integers $$$A_1, A_2, ..., A_N$$$ $$$(1 \le A_i \le 20)$$$.

Output

Print one integer — the minimum possible value of $$$B_1 + B_2 + ... + B_N$$$.

Example
Input
6
1 2 3 4 5 6
Output
147

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

Yehia gave Omar a square 2D array of size $$$N$$$ x $$$N$$$. He wants Omar to count the number of nodes in a Quad Tree built from this array.

Definition – Quad Tree

A Quad Tree is a tree built recursively as follows: (see Notes for visualization)

  • Each node represents a square submatrix.
  • If all elements in the submatrix are equal, the node is a leaf node.
  • Otherwise, the matrix is split equally into 4 quadrants (top-left, top-right, bottom-left, bottom-right), and each quadrant becomes a child node. This process continues recursively until all nodes are leaf nodes.

Your task is to determine the total number of nodes (both internal and leaf nodes) in the Quad Tree.

Input

The first line contains an integer $$$N$$$ ($$$1 \le N \le 512$$$, $$$N$$$ is guaranteed to be a power of $$$2$$$).

The next $$$N$$$ lines each contain $$$N$$$ integers $$$A[i][j]$$$ ($$$A[i][j]$$$ is either $$$0$$$ or $$$1$$$) — the elements of the 2D array.

Output

Print a single integer: the total number of nodes in the Quad Tree.

Examples
Input
4
0 1 1 1
1 1 1 0
0 0 0 1
0 0 0 1
Output
17
Input
2
0 0
0 0
Output
1
Input
8
0 0 0 0 1 0 0 1
1 0 0 1 0 0 1 0
0 1 1 0 0 0 1 1
1 0 1 1 1 1 0 1
0 0 0 1 0 0 0 0
1 1 1 1 1 0 0 0
0 0 1 1 0 0 1 1
1 1 0 1 0 0 1 0
Output
77
Note

The tree formed for test case 1 is as follows

The second testcase will form only one node (root node) because it all has the same value.

J. Zaghloul and the spies
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

During the 1919 revolution, Zaghloul noticed that there were spies hiding among the Egyptians. He tasked Zeyad with finding them to save Egypt.

There are $$$n$$$ people standing in a row. The $$$i$$$-th person holds an integer $$$a_i$$$. A person is considered a spy if the bitwise XOR sum of all divisors of their number $$$a_i$$$ is divisible by $$$k$$$.

You need to answer $$$q$$$ queries. For each query, find the number of spies in the range $$$[l, r]$$$.

Input

The first line contains three integers $$$n$$$, $$$q$$$, and $$$k$$$ ($$$1 \le n, q, k \le 10^6$$$) — the number of people, the number of queries, and the divisor check value.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^6$$$) — the numbers held by the people.

Each of the next $$$q$$$ lines contains two integers $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le n$$$) — the range of the query.

Output

For each query, find the number of spies in the range.

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

K. Wala matgeesh bra7tek howa enty hatzeleniiiii
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Baraa was watching a series called "Fahd el Batal" on television with his grandpa when he suddenly got an idea for an interesting problem. You are given an array $$$a$$$ of length $$$n$$$ and two integers $$$x$$$ and $$$y$$$. Count the number of pairs $$$(i, j)$$$ with $$$1 ≤ i \lt j ≤ n$$$ such that $$$x ≤ gcd(a_i, a_j)$$$.

When Baraa gave the problem to Ziad, Fady — as usual — argued and changed it to counting pairs $$$(i, j)$$$ with $$$lcm(a_i, a_j) ≤ y,$$$ but Baraa refused. So Ziad — as usual — used his wisdom to end the argument and declared that the task should be to count pairs $$$(i, j)$$$ with $$$1 ≤ i \lt j ≤ n$$$ satisfying $$$x ≤ gcd(a_i, a_j) ≤ lcm(a_i, a_j) ≤ y.$$$

Baraa is too d3eef to solve this problem, so he asks you to solve it.

Input

The first line contains three integers $$$n$$$, $$$x$$$, and $$$y$$$ ($$$1 \le n, x, y \le 10^5$$$) — the size of the array, and the parameters described in the statement.

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

Output

Print a single integer — the number of pairs $$$(i, j)$$$ ($$$1 \le i \lt j \le n$$$) that satisfy $$$x \le gcd(a_i, a_j) \le \operatorname{lcm}(a_i, a_j) \le y.$$$

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