1001 Maximum Multiple

Problem Description

Given an integer n, Chiaki would like to find three positive integers x, y and z such that: $n=x+y+z$, $x\mid n$, $y \mid n$, $z \mid n$ and $xyz$ is maximum.

Input

There are multiple test cases. The first line of input contains an integer $T$ ($1 \le T \le 10^6$), indicating the number of test cases. For each test case:
The first line contains an integer $n$ ($1 \le n \le 10^{6}$).

Output

For each test case, output an integer denoting the maximum $xyz$. If there no such integers, output $-1$ instead.

3

1

2

3

-1

-1

1

1011 Time Zone

Problem Description

Chiaki often participates in international competitive programming contests. The time zone becomes a big problem. Given a time in Beijing time (UTC +8), Chiaki would like to know the time in another time zone s.

Input

There are multiple test cases. The first line of input contains an integer $T$ ($1 \le T \le 10^6$), indicating the number of test cases. For each test case:
The first line contains two integers $a$, $b$ ($0 \le a \le 23, 0 \le b \le 59$) and a string $s$ in the format of "UTC+X’’, "UTC-X’’, "UTC+X.Y’’, or "UTC-X.Y’’ ($0 \le X, X.Y \le 14, 0 \le Y \le 9$).

Output

For each test, output the time in the format of $hh:mm$ (24-hour clock).

3

11 11 UTC+8

11 12 UTC+9

11 23 UTC+0

11:11

12:12

03:23

1003 Triangle Partition

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 132768/132768 K (Java/Others)

Special Judge

Problem Description

Chiaki has 3n points p1,p2,…,p3n. It is guaranteed that no three points are collinear. Chiaki would like to construct n disjoint triangles where each vertex comes from the 3n points.

Input

There are multiple test cases. The first line of input contains an integer $T$, indicating the number of test cases. For each test case:
The first line contains an integer $n$ ($1 \le n \le 1000$) – the number of triangle to construct.
Each of the next $3n$ lines contains two integers $x_i$ and $y_i$ ($-10^9 \le x_i, y_i \le 10^9$).
It is guaranteed that the sum of all $n$ does not exceed $10000$.

Output

For each test case, output $n$ lines contain three integers $a_i,b_i,c_i$ ($1 \le a_i,b_i,c_i \le 3n$) each denoting the indices of points the $i$-th triangle use. If there are multiple solutions, you can output any of them.

1

1

1 2

2 3

3 5

1 2 3

1004 Distinct Values

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Problem Description

Chiaki has an array of $n$ positive integers. You are told some facts about the array: for every two elements $a_i$ and $a_j$ in the subarray $a_{l..r}$ ($l \le i \lt j \le r$), $a_i \ne a_j$ holds.
Chiaki would like to find a lexicographically minimal array which meets the facts.

Input

There are multiple test cases. The first line of input contains an integer $T$, indicating the number of test cases. For each test case:

The first line contains two integers $n$ and $m$ ($1 \le n, m \le 10^5$) – the length of the array and the number of facts. Each of the next $m$ lines contains two integers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le n$).

It is guaranteed that neither the sum of all $n$ nor the sum of all $m$ exceeds $10^6$.

Output

For each test case, output $n$ integers denoting the lexicographically minimal array. Integers should be separated by a single space, and no extra spaces are allowed at the end of lines.

3

2 1

1 2

4 2

1 2

3 4

5 2

1 3

2 4

1 2

1 2 1 2

1 2 3 1 1

❤采之欲遗谁，所思在远道。❤