Minimum Path Sum to Target in Binary Tree

Among all root-to-leaf paths in the binary tree whose sum equals target, first choose the one with the fewest nodes, then the one whose sequence of node values is lexicographically smallest. If there is no solution, output an empty array.

输入格式

The first line contains m, the number of level-order token entries, and target; the second line contains m integers or null. Entries are interpreted in order as the left and right children of the non-null parents taken from a queue; trailing null tokens may be omitted, and full heap indices are not used. The original gave no numeric bounds; this site uses 0..100000 nodes, 0≤m≤200001, node values within ±10^9, and target within ±10^14; a valid level order is guaranteed, and an empty tree can be given as m=0 or a single null.

输出格式

The first line contains the number of nodes on the path, and the second line contains the values on the path; if there is no solution, output only 0.

样例 1

输入：

13 22
5 4 8 11 null 13 4 7 2 null null 5 1

输出：

4
5 4 11 2

样例 2

输入：

3 5
1 2 3

输出：

0

样例 3

输入：

7 0
0 2 1 -2 null null -1

输出：

3
0 1 -1

样例说明

The outputs of the three public examples are, in order: 4 / 5 4 11 2; 0; 3 / 0 1 -1. These answers were verified by independent enumeration or direct simulation.