题目背景

原题链接：https://oier.team/problems/88

题目描述

现在有 $0 \sim n$ 共 $n + 1$ 个数。 定义 $(x)_{3}$ 表示十进制数 $x$ 的三进制形式。如果没有特别强调，那么这些数均为十进制形式。

youyou 想构造一个序列长度为 $p$（$p \ge 1$）的非负整数序列 $a$。使之满足：

• $a_i \in [0,n]$。
• 不存在 $i,j$（$1 \le i <j \le p$），使得 $a_i = a_j$。
• 对于任意 $1 \le i < n$，$a_i$ 与 $a_{i+1}$ 至少满足以下四个条件中的一个：
  1. $(a_i)_3$ 去掉最后一位，恰好等于 $(a_{i+1})_3$（若只有一位，则去掉后的数字为 $0$）。
  2. 在 $(a_i)_3$ 末尾添上某一位 $t(0 \le t \le 2)$，恰好等于 $(a_{i+1})_3$（若 $a_i = 0$，则添加后舍去前置 $0$）。
  3. $a_i \le w$， $(a_i)_3$ 的末尾不是 $0$，且将末尾的一位数字移到开头与 $(a_{i + 1})_3$ 相等。
  4. 当 $(a_i)_3$ 长度 $\ge 2$，且 $(a_i)_3$ 次高位非零时，将 $(a_i)_3$ 开头的一位数字移到末尾，形成的数的十进制值 $\le w$，且恰好等于 $(a_{i+1})_3$。

这样的序列 $a$ 被称为“完美的”。

youyou 认为，如果十进制三元组 $(x,y,z)$ 是好的，必须满足以下条件：

• $0 \le x,y,z \le n$，$x \neq y$。
• 存在至少一个”完美的“序列 $b$，使得十进制下有 $b_1=x$，$b_s = y$。其中 $s$ 为序列长度。
• 存在至少一个”完美的”序列 $c$，使得十进制下有 $c_1=z$。同时，对于上述任意的 $b$，均有恰好一对 $(i, j)$，满足 $1 \le i \le |b|$，$1 \le j \le |c|$，使得 $b_i = c_j$。

对于每一个 $0 \le z \le n$，求能构成“好的”三元组 $(x,y,z)$ 的有序对 $(x,y)$ 的个数。

输入格式

仅一行，为一个正整数 $n$ 和一个非负整数 $w$，其含义在题目描述中给出。

输出格式

共 $n + 1$ 行，其中第 $i + 1$ 行一个数表示当 $z = i$ 时，能构成“好的”三元组 $(x,y,z)$ 的有序对 $(x,y)$ 的个数。

4 3

20
20
20
20
20

提示

【样例解释 #1】

一共有 $5$ 个数，用三进制表示分别为 $0,1,2,10,11$。

当 $z = 0,1,2,3,4$ 时，全部 $(x,y)(x \neq y)$ 数对均满足题意。

下面给出三元组 $(2,3,1)$ 是“好的”的证明。

当 $x=2,y=3,z=1$ 时，序列 $b$ 可以为 $\{2,0,1,3\}$。

其中 $b_1,b_2$ 满足条件 $1$，$b_2,b_3$ 满足条件 $2$，$b_3,b_4$ 满足条件 $2$。

可以证明只有这一个序列 $b$ 满足题意。因此，存在 $c = \{1\}$，使得 $B \cap C = \{1\}$。所以 $(2,3,1)$ 是“好的”三元组。

【样例 #2】

见附件中的 ternary/ternary2.in 与 ternary/ternary2.ans。

该组样例满足测试点 $4\sim 6$ 的约束条件。

【样例 #3】

见附件中的 ternary/ternary3.in 与 ternary/ternary3.ans。

该组样例满足测试点 $7\sim 10$ 的约束条件。

【样例 #4】

见附件中的 ternary/ternary4.in 与 ternary/ternary4.ans。

该组样例满足测试点 $13\sim 15$ 的约束条件。

【样例 #5】

见附件中的 ternary/ternary5.in 与 ternary/ternary5.ans。

该组样例满足测试点 $20\sim 25$ 的约束条件。

【数据范围】

本题共 $25$ 个测试点，每个 $4$ 分。

测试点编号	$n$	$w$	特殊性质
$1 \sim 3$	$\le 18$		无
$4 \sim 6$	$\le 242$
$7 \sim 10$	$\le 6560$	$\le6560$
$11\sim12$	$\le 10^5$	$\le 10^5$
$13\sim15$	$\le 3 \times 10^5$		有
$16\sim 17$		$=0$	无
$18\sim 19$		$=n$
$20\sim25$		$\le 3 \times 10^5$

特殊性质：$w \ge 10^4$。

对于全部数据，保证：$1\le n \le 3 \times 10^5$，$0 \le w \le n$。