NWU IUPC 2025 powered by CPS Academy
A. Secret Code Printer
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

A secret organization uses a special code to identify skilled programmers. The code is derived from the first letters of the words Competitive Programming Skills.

Your task is to write a program that prints this secret code.

Input

There is no input for this problem.

Output

Print the secret code on a single line.

Example
Input
There is no input
Output
CPS

B. A King With No Name
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Killua is a smart anime character who enjoys playing chess. However, in his world, the chess pieces behave a bit differently. He currently has a special piece called a $$$Half-Queen$$$. Its movement follows these rules:

  1. It cannot move outside the board, which has $$$N$$$ rows and $$$N$$$ columns, with the upper-leftmost cell being $$$(0, 0)$$$.
  2. It cannot move through other pieces (no jumping over pieces).
  3. It can move horizontally and along the minor diagonal. Meaning if it is currently on cell $$$(x, y)$$$, it can move to either $$$(x + i, y - i)$$$ or $$$(x, y + i)$$$, for all integers $$$i \in \mathbb{Z}$$$, as long as the previous two conditions remain valid.
Figure 1. Example of the Half-Queen's (at cell x=4,y=2) possible movement.

You are given an $$$N×N$$$ chessboard. One cell contains Killua's half-queen, and another cell contains an enemy King. Other cells may be empty or may contain pieces (which cannot be captured or crossed).

Your task is to determine the minimum number of moves required for the Half-Queen to reach the enemy King without capturing or passing through any other piece. If it is impossible to reach the King, report that.

Input

The first line will contain an integer $$$N$$$ ($$$2\le N \le 1000$$$). The next $$$N$$$ lines each contain a string of length $$$N$$$, representing the board. The board contains:

  • "Q" — the Half-Queen
  • "K" — the enemy King
  • "." — an empty cell
  • "#" — a piece
Output

Print the minimum number of moves required for the Half-Queen to reach the enemy King. If it is impossible, print -1.

Examples
Input
4
.K..
....
..Q.
....
Output
3
Input
4
.K#.
#...
..Q.
....
Output
-1

C. Square Free GCD Sum
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$a$$$ of $$$n$$$ positive integers $$$a_1,$$$ $$$a_2,$$$ ... $$$,a_n$$$. You are also given $$$m$$$ distinct primes $$$p_1,$$$ $$$p_2,$$$ ... $$$,p_m$$$.

It is guaranteed that every $$$a_i$$$ can be expressed as

$$$a_i = \displaystyle \prod_{j=1}^{m} p_j^{e_{i,j}}, \quad e_{i,j} \geq 0.$$$

That is$$$,$$$ all prime factors of all numbers are among these $$$m$$$ primes.

For any non-empty subset $$$S \subseteq \{1, 2, ..., n\},$$$ let gcd($$$S$$$) = gcd($$$a_i \; | \; i \in S$$$). That is, gcd(S) is the greatest common divisor of all elements of the array $$$a$$$ with their index in that subset.

Define a function $$$sf(x)$$$ – the squarefree part of an integer $$$x$$$ as the product of all distinct primes dividing $$$x$$$. For example:

  • $$$sf(12) = 2 \times 3 = 6$$$ – because $$$2$$$ and $$$3$$$ are the distinct primes that divide $$$12$$$
  • $$$sf(18) = 2 \times 3 = 6$$$
  • $$$sf(1) = 1$$$

Your task is to compute, the sum of squarefree parts of gcds over all non-empty subsets of $$$a$$$. Formally, you have to find the following value:

$$$\displaystyle \sum_{\emptyset \neq S \subseteq \{1, 2, ..., n\}}^{} sf(gcd(S))$$$ mod ($$$10^9 + 7$$$)
Input

First line contains $$$2$$$ integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \leq 10^5$$$), ($$$1 \leq m \leq 20$$$).

The second line contains $$$m$$$ space-separated integers $$$p_1,$$$ $$$p_2,$$$ ... $$$,p_m$$$ ($$$1 \leq p_i \leq 200$$$).

The third line contains $$$n$$$ space-separated integers $$$a_1,$$$ $$$a_2,$$$ ... $$$,a_n$$$ ($$$1 \leq a_i \leq 10^9$$$).

Output

Output one integer, the required sum mod ($$$10^9 + 7$$$)

Examples
Input
4 3
2 3 5
2 6 10 30
Output
82
Input
1 1
2
8
Output
2

D. GCD of Pairs
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

It was the last hour before the regional contest scoreboard froze. The team from Aurora University had one problem left to test: their coach tossed two arrays onto the screen and challenged them with a playful quiz.

"You know your usual gcd tricks," she said while stirring her coffee, "but here's a twist — count how often a greatest common divisor is prime. If you can do that quickly, I'll let you grab the first slice of victory pizza."

The team smiled and started typing. Now it's your turn.

You are given two arrays $$$a$$$ and $$$b$$$ of length $$$n$$$. Compute the number of ordered pairs $$$(i, j)$$$ such that $$$1 \le i \le n$$$, $$$1 \le j \le n$$$, and $$$\gcd(a_i, b_j)$$$ is a prime number.

Input

The first line contains a single integer $$$T$$$ $$$(1 \le T \le 10^5)$$$ — the number of test cases.

Each test case consists of the following:

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

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

The third line contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$ $$$(1 \le b_i \le n)$$$.

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

Output

For each test case, print a single integer — the number of ordered pairs $$$(i,j)$$$ such that $$$\gcd(a_i, b_j)$$$ is a prime.

Examples
Input
5
5
1 3 5 4 4
2 3 2 1 2
2
1 1
2 2
2
1 1
2 2
3
1 2 1
2 2 3
5
4 2 2 5 4
2 1 2 5 3
Output
7
0
0
2
9
Input
5
10
8 6 4 6 9 7 2 3 6 2
6 7 4 6 10 1 6 6 3 3
5
2 3 3 2 2
2 2 3 4 4
4
3 4 1 3
1 2 4 1
3
3 1 1
2 3 2
2
2 1
1 2
Output
47
14
1
1
1

E. XOR Subarray Minimization
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given $$$t$$$ independent test cases. In each test case, you are given an array of $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$.

You can perform the following operation at most once for each integer $$$k$$$ such that $$$2^k \le n$$$:

  • Choose a contiguous subarray of length exactly $$$2^k$$$.
  • For every element $$$a_i$$$ in that subarray, replace it with $$$a_i \leftarrow a_i \oplus 2^k$$$, where $$$\oplus$$$ denotes the bitwise XOR operation.

Your task is to determine the minimum possible sum of the array elements after performing these operations optimally, given that for each valid $$$k$$$, the corresponding operation may be performed at most once (and possibly not at all).

Input

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

Each test case consists of two lines:

  • The first line contains an integer $$$n$$$ $$$(1 \le n \le 10^5)$$$ — the number of elements in the array.
  • The second line contains $$$n$$$ space-separated integers $$$a_1, a_2, \dots, a_n$$$ $$$(0 \le a_i \lt 2^{30})$$$.

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

Output

For each test case, print a single integer — the minimum sum of the array that can be obtained after performing the operations optimally.

Example
Input
5
1
10
4
1 5 4 5
5
9 4 9 5 2
2
3 3
1
3
Output
10
6
28
1
2

F. Count Pairs
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You will be asked $$$Q$$$ queries. In each query, you will be given an integer number $$$k$$$ and you have to find out the number of ordered integer pairs($$$x,y$$$) satisfying the equation, $$$x^2+y^2 \le k$$$.

Input

$$$1 \le Q \le 10^5$$$

$$$-10^3\le k\le 10^3$$$

Output

For each query, print an integer the number of ordered interger pairs($$$x,y$$$) satisfying the equation, $$$x^2+y^2 \le k$$$.

Example
Input
3
2
0
5
Output
9
1
21

G. Tightest Two-Beacon
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

A surveillance drone is analyzing a field with $$$n$$$ distinct beacon towers located at various coordinates on a 2D map. The drone may select any three distinct towers to form a triangular frame.

A triangle formed by three towers $$$A$$$, $$$B$$$, and $$$C$$$ is called a valid frame if it satisfies the following geometric condition:

When you extend each of the three sides of triangle $$$ABC$$$ infinitely in both directions (turning them into full lines):

  • Exactly one of those three lines has two of the given towers (from the entire set of $$$n$$$ towers) lying on it, and
  • All the remaining towers lie strictly on one side of that line.

The other two lines also have two towers lying on them, but in those cases, the remaining towers are not all on the same side — that is, some towers lie on one side and some on the other.

For every tower $$$P$$$, define its stability score as the smallest area of any valid frame (triangle) that includes $$$P$$$ as one of its vertices.

Your task is to determine the largest stability score among all towers that can form valid frames.

Input

The first line contains one integer $$$n$$$ ($$$4 \le n \le 5000$$$) — the number of towers. Each of the next $$$n$$$ lines contains two integers $$$x$$$ and $$$y$$$ ($$$-10^6 \le x, y \le 10^6$$$) — the coordinates of each tower.

All coordinates are unique, and no three points are colinear.

Output

Print the largest stability score in one line. If no valid frame is possible, print 0.

Your answer will be considered correct if the absolute error is less than $$$10^{-4}$$$.

Examples
Input
8
-4 3
-6 11
4 -12
-10 -18
20 20
19 -8
-10 13
14 11
Output
93.0000000000
Input
4
-5 4
6 2
3 -5
-12 1
Output
0.0000000000