For given $n$ and $k$, you need to construct a matrix $A_{i,j}$ consisting only of $0$ and $1$, where $0 \le i, j \le n$, satisfying the following conditions:
- $A_{i,i}=1$.
- $A_{i,i+1}=1$.
- For $i > j$, $A_{i,j}=0$.
- If $A_{i,j}=1$ and $j-i > 1$, then there exists $i < t < j$ such that $A_{i,t}=A_{t,j}=1$.
- For $i \le j$, $(A^k)_{i,j} > 0$.
You need to output every pair $(i, j)$ such that $A_{i,j}=1$ and $j-i > 1$. Let $m$ be the total number of such pairs.
If the output does not satisfy the requirements, you will not receive any points for that test case. If the output satisfies the requirements, you will be scored based on $m$.
Input
A single line containing two integers $n$ and $k$.
Output
The first line contains an integer $m$. The next $m$ lines each contain two integers $i$ and $j$, representing each pair $(i, j)$ such that $A_{i,j}=1$ and $j-i > 1$.
Examples
Input 1
3 2
Output 1
1 0 2
Constraints
| $k$ | $f(k)$ | $s(k)$ |
|---|---|---|
| 2 | 7.9870 | 22 |
| 3 | 3.8085 | 14 |
| 4 | 2.3960 | 11 |
| 5 | 1.9610 | 9 |
| 6 | 1.6065 | 7 |
| 7 | 1.4515 | 6 |
| 8 | 1.2540 | 5 |
| 9 | 1.1980 | 5 |
| 10 | 1.0995 | 4 |
| 11 | 1.0705 | 4 |
| 12 | 1.0345 | 4 |
| 13 | 1.0120 | 3 |
| 14 | 1.0015 | 3 |
| 15 | 0.9940 | 3 |
For all test cases, $1900 \le n \le 2000$ and $2 \le k \le 15$.
Each $k$ in the range $2 \le k \le 15$ corresponds to a subtask with a total score of $s(k)$. The score for each subtask is the minimum of the scores of all test cases within that subtask.
The score for each test case is $\max\left(0, 1 - \sqrt{\max\left(0, \frac{m}{n \cdot f(k)} - 1\right)}\right)$ times the total score of the subtask.