Background

Original link: https://oier.team/problems/S4D。

Problem Description

There are $n + 1$ numbers from $0$ to $n$.

Let $(x)_{3}$ denote the ternary representation of the decimal number $x$. Unless explicitly stated otherwise, all numbers are in decimal form.

youyou wants to construct a non-negative integer sequence $a$ of length $p$ ($p \ge 1$), such that:

• $a_i \in [0,n]$。
• There do not exist $i,j$ ($1 \le i < j \le p$) such that $a_i = a_j$。
• For any $1 \le i < n$, $a_i$ and $a_{i+1}$ satisfy at least one of the following four conditions:
  1. Remove the last digit of $(a_i)_3$, and it becomes exactly $(a_{i+1})_3$ (if there is only one digit, then after removing it the number becomes $0$)。
  2. Append a digit $t(0 \le t \le 2)$ to the end of $(a_i)_3$, and it becomes exactly $(a_{i+1})_3$ (if $a_i = 0$, then after appending, leading $0$ is discarded)。
  3. $a_i \le w$, the last digit of $(a_i)_3$ is not $0$, and moving the last digit to the front makes it equal to $(a_{i + 1})_3$。
  4. When the length of $(a_i)_3$ is $\ge 2$ and the second highest digit of $(a_i)_3$ is non-zero, move the first digit of $(a_i)_3$ to the end; the decimal value of the resulting number is $\le w$, and it is exactly equal to $(a_{i+1})_3$。

Such a sequence $a$ is called "perfect".

youyou believes that a decimal triple $(x,y,z)$ is good if and only if it satisfies all of the following conditions:

• $0 \le x,y,z \le n$, and $x \neq y$。
• There exists at least one "perfect" sequence $b$ such that in decimal we have $b_1 = x$ and $b_s = y$, where $s$ is the length of the sequence。
• There exists at least one "perfect" sequence $c$ such that in decimal we have $c_1 = z$. At the same time, for any $b$ mentioned above, there is exactly one pair $(i, j)$ satisfying $1 \le i \le |b|$ and $1 \le j \le |c|$ such that $b_i = c_j$。

For each $0 \le z \le n$, find the number of ordered pairs $(x,y)$ that can form a good triple $(x,y,z)$.

Input Format

One line containing a positive integer $n$ and a non-negative integer $w$, whose meanings are given in the statement.

Output Format

Output $n + 1$ lines. The $(i + 1)$-th line contains one number, indicating that when $z = i$, the number of ordered pairs $(x,y)$ that can form a good triple $(x,y,z)$.

4 3

20
20
20
20
20

Hint

[Sample Explanation #1]

There are $5$ numbers, whose ternary representations are $0,1,2,10,11$ respectively.

When $z = 0,1,2,3,4$, all pairs $(x,y)$ with $x \neq y$ satisfy the requirement.

Below is a proof that the triple $(2,3,1)$ is good.

When $x = 2, y = 3, z = 1$, the sequence $b$ can be $\{2,0,1,3\}$.

Here, $b_1,b_2$ satisfy condition $1$, $b_2,b_3$ satisfy condition $2$, and $b_3,b_4$ satisfy condition $2$.

It can be proved that only this sequence $b$ satisfies the requirement. Therefore, there exists $c = \{1\}$ such that $B \cap C = \{1\}$. Hence $(2,3,1)$ is a good triple.

[Sample #2]

See ternary/ternary2.in and ternary/ternary2.ans in the attachment.

This sample satisfies the constraints of test points $4 \sim 6$.

[Sample #3]

See ternary/ternary3.in and ternary/ternary3.ans in the attachment.

This sample satisfies the constraints of test points $7 \sim 10$.

[Sample #4]

See ternary/ternary4.in and ternary/ternary4.ans in the attachment.

This sample satisfies the constraints of test points $13 \sim 15$.

[Sample #5]

See ternary/ternary5.in and ternary/ternary5.ans in the attachment.

This sample satisfies the constraints of test points $20 \sim 25$.

[Constraints]

This problem has $25$ test points, $4$ points each.

Special property: $w \ge 10^4$。

For all data, it is guaranteed that $1 \le n \le 3 \times 10^5$ and $0 \le w \le n$。

Translated by ChatGPT 5