Counting Good Triplets in a Ternary Transformation Graph

We are given two non‐negative integers n and w. Consider the set of integers from 0 to n (a total of n+1 numbers). For any integer x, let \(f(x)\) denote the ternary representation of x written in base \(3\) without leading zeroes (with \(f(0)=\mathtt{0}\)).

Define four operations between two numbers \(a\) and \(b\) (written in their ternary representations) as follows. We say there is a directed edge from \(a\) to \(b\) if at least one of the following conditions is satisfied (all numbers are considered in decimal unless otherwise stated):

1. Truncation: Let \(s=f(a)\). Remove its last digit. (If \(s\) has only one digit then the result is defined as "0".) If the resulting string equals \(f(b)\), then the edge \(a\to b\) exists.
2. Extension: For any digit \(t\) (with \(0\le t\le2\)): if \(a\neq0\) then append \(t\) to \(s=f(a)\) (i.e. form \(s\Vert t\)); if \(a=0\) then after appending \(t\) to "0" remove the extra leading zero so that the result is \(t\) (with the convention that if \(t=0\) we have "0"). If the resulting string equals \(f(b)\), then an edge \(a\to b\) exists.
3. Right‐rotation: If \(a \le w\) and the last digit of \(f(a)\) is not \(0\), let \(s=f(a)\) and form a new string by moving its last digit to the front (i.e. \(s_{new}=\text{last}(s)\Vert \text{prefix}(s)\)). If \(f(b)=s_{new}\), then there is an edge \(a\to b\).
4. Left‐rotation: If \(f(a)\) has length at least 2 and its second digit is not \(0\), form the string by moving the first digit to the end (i.e. \(s_{new}=\text{suffix}(s)\Vert \text{first}(s)\)). Convert \(s_{new}\) to its decimal value and if that value is \(\le w\) and \(f(b)=s_{new}\), then there is an edge \(a\to b\).

A sequence of distinct non‐negative integers \(a_1,a_2,\dots,a_p\) (with \(p\ge 1\)) is called perfect if for every consecutive pair \(a_i\) and \(a_{i+1}\) (\(1\le i<p\)) there is a directed edge from \(a_i\) to \(a_{i+1}\) (i.e. at least one of the above conditions holds). Note that all numbers are in decimal unless stated otherwise.

Now, consider a decimal triplet \((x,y,z)\) (with \(0\le x,y,z\le n\) and \(x\ne y\)). We say that \((x,y,z)\) is good if:

• There exists at least one perfect sequence \(b\) with \(b_1=x\) and \(b_{s}=y\) for some length \(s\ge 1\).
• There exists at least one perfect sequence \(c\) with \(c_1=z\). (Note that the trivial sequence \([z]\) is always a perfect sequence.)
• For every perfect sequence \(b\) from \(x\) to \(y\), there is exactly one pair of indices \((i,j)\) (with \(1\le i\le |b|\) and \(1\le j\le |c|\)) such that \(b_i=c_j\). In other words, every perfect sequence from \(x\) to \(y\) must contain \(z\) exactly once.

Your task is: For each \(z\) with \(0\le z\le n\), count the number of ordered pairs \((x,y)\) (with \(x\ne y\)) such that \((x,y,z)\) is good.

---

Input

• The input consists of two integers n and w.

---

Output

• Output \(n+1\) lines. The \(i\)th line (starting from \(i=0\)) should contain a single integer: the number of ordered pairs \((x,y)\) (with \(x\ne y\)) such that the triplet \((x,y,i)\) is good.

---

Note on the Problem Transformation

If we define a directed graph \(G\) on vertices \(0,1,\dots,n\) where there is an edge from \(a\) to \(b\) if any of the above four conditions is satisfied by their ternary representations, then a perfect sequence is just a simple (no repeated vertices) path in \(G\). Also, the condition that every perfect sequence from \(x\) to \(y\) contains \(z\) (exactly once) is equivalent to saying that for every simple path from \(x\) to \(y\) in \(G\), the vertex \(z\) appears. (Note that in any simple path, any vertex appears at most once.)

Thus the problem reduces to, for each candidate \(z\), counting the pairs \((x,y)\) (with \(x\ne y\)) for which there exists a path from \(x\) to \(y\) in \(G\) and, when vertex \(z\) is removed from \(G\), no path from \(x\) to \(y\) exists (unless \(x=z\) or \(y=z\), in which case the path trivially contains \(z\)).

inputFormat

The input consists of a single line containing two space‐separated integers n and w.

outputFormat

Output n+1 lines. The i-th line (with i starting from 0) should contain a single integer representing the number of ordered pairs \((x,y)\) (with \(x\ne y\)) such that the triplet \((x,y,i)\) is good.

sample

2 2

6
4
4

</p>