Setsuna has been fascinated by coprime pairs recently, so she decided to play a game about numbers.
Here are $n$ integers $a_1, a_2, \\\\cdots, a_n (2 <= a_i <= 10^(18))$. Setsuna wants to divide the numbers into as few groups as possible so that each number is exactly in one group and the numbers in each group are coprime with each other.
We say that positive integers $x$ and $y$ are coprime if and only if $gcd (x, y) = 1$, where $gcd (x, y)$ refers to their greatest common divisor.
However, Setsuna is not good at math, so she only comes up with a fake algorithm.
Her greedy algorithm is obviously wrong, so we need to hack her solution.
You are given one integer $k$. You need to find the input consisting of $n (n <= 300)$ integers and a corresponding partition to the input(*not necessarily* be the minimum partition), which satisfies $X = Y + k$, where $Y$ is the number of groups of your partition and $X$ is the answer of her algorithm to your input.
It can be proved that the answer always exists.
The input contains one integer $k (1 <= k <= 7)$.
In the first line, output two integers $n, Y (1 <= Y <= n <= 300)$.
In the second line, output $n$ integers $a_1, a_2, \\\\cdots, a_n (2 <= a_i <= 10^(18))$, separated by spaces.
In the third line, output $n$ integers $G_1, G_2, \\\\cdots, G_n (1 <= G_i <= Y)$, separated by spaces, where $g_i$ indicates which group is $a_i$ divided into.
If there are multiple solutions, you can output any.
In the sample, Setsuna will get $3$ groups: ${8, 3}, {45}, {100}$, but we have a better partition: ${8, 45}, {3, 100}$.
## Input
The input contains one integer $k (1 <= k <= 7)$.
## Output
In the first line, output two integers $n, Y (1 <= Y <= n <= 300)$.In the second line, output $n$ integers $a_1, a_2, \\\\cdots, a_n (2 <= a_i <= 10^(18))$, separated by spaces.In the third line, output $n$ integers $G_1, G_2, \\\\cdots, G_n (1 <= G_i <= Y)$, separated by spaces, where $g_i$ indicates which group is $a_i$ divided into.If there are multiple solutions, you can output any.
[samples]
## Note
In the sample, Setsuna will get $3$ groups: ${8, 3}, {45}, {100}$, but we have a better partition: ${8, 45}, {3, 100}$.
**Definitions**
Let $ a, b, c \in \{0, 1, \dots, 9\} $ be the allowed digits.
Let $ \mathcal{D} = \{a, b, c\} $ be the set of permitted digits.
A number $ n \geq 10 $ is a *Perfect Rose* if:
- All its digits belong to $ \mathcal{D} $,
- It contains no leading zeros,
- One of its digits equals the arithmetic mean of all other digits.
Let $ q \in \mathbb{Z}^+ $ be the number of shops.
For each shop $ k \in \{1, \dots, q\} $, let $ [L_k, R_k] $ be the range of rose numbers sold, with $ 0 \leq L_k \leq R_k \leq 10^9 $.
**Constraints**
1. $ 1 \leq q \leq 10^5 $
2. $ 0 \leq a, b, c \leq 9 $
3. $ 0 \leq L_k \leq R_k \leq 10^9 $ for all $ k \in \{1, \dots, q\} $
4. Numbers must not have leading zeros.
5. 1-digit numbers are excluded from being Perfect Roses.
**Objective**
For each shop $ k $, compute:
$$
P_k = \left| \left\{ n \in [L_k, R_k] \mid n \text{ is a Perfect Rose} \right\} \right|
$$
Find the shop index $ k^* = \min \left\{ k \in \{1, \dots, q\} \mid P_k = \max_{1 \leq j \leq q} P_j \right\} $.
Output $ k^* $.