"Turtle Blind Box" is a popular blind box game on online platforms. Meiyangyang is very addicted to this game, so Yangyang has prepared a total of $k$ turtle blind boxes for her to play with.

"Turtle Blind Box" is played on a $3 \times 3$ grid. Each cell has a number, where cell 1 is the "special cell" and the others are "non-special cells", as shown below:

Figure 1: Grid numbering

The turtles in the blind boxes are of two types: one is a regular turtle, where the style (mainly color) of each turtle is one of $m$ types, represented by numbers $1 \sim m$; the other is a hidden turtle, represented by the number $0$.

At the beginning of the game, there are no turtles on the grid. Yangyang gives Meiyangyang $n$ unopened turtle blind boxes, and Meiyangyang chooses a regular turtle style $t$ as her lucky color.

In each round, Meiyangyang performs the following operations in order:

1. Starting from cell 1 up to cell 9, if the current cell is empty and Meiyangyang still has unopened turtle blind boxes, Meiyangyang takes a turtle blind box from the unopened ones, opens it, and places the turtle into the current cell.
   • If the color of the opened turtle matches Meiyangyang's chosen lucky color, Yangyang rewards Meiyangyang with 1 extra unopened turtle blind box.
   • If the opened turtle is a hidden turtle, Meiyangyang immediately takes this turtle, and Yangyang rewards Meiyangyang with 1 extra unopened turtle blind box, ending the current round.
2. If all 9 cells on the grid are occupied and the turtles in these cells are all distinct, Meiyangyang takes the turtle in cell 1, and the current round ends.
3. If there are 3 turtles of the same color in a straight line (horizontal, vertical, or diagonal), Meiyangyang takes the turtles in the non-special cells, and Yangyang rewards Meiyangyang with 5 extra unopened turtle blind boxes. Repeat this step until no 3 turtles of the same color are in a straight line.
   • If there are multiple sets of 3 turtles satisfying the condition, prioritize taking the set with the smaller minimum cell number; if the minimum cell numbers are the same, prioritize taking the set with the smaller maximum cell number.
4. If there are 2 turtles of the same color in a straight line, Meiyangyang takes the turtles in the non-special cells, and Yangyang rewards Meiyangyang with 1 extra unopened turtle blind box. Repeat this step until no 2 turtles of the same color are in a straight line.
   • If there are multiple sets of 2 turtles satisfying the condition, prioritize taking the set with the smaller minimum cell number; if the minimum cell numbers are the same, prioritize taking the set with the smaller maximum cell number.
5. If the operations in steps 3 and 4 involve the special cell, Meiyangyang takes the turtle in the special cell.
6. If no operations were performed in steps 1 through 5, the game ends, and Meiyangyang takes all remaining turtles on the grid. Otherwise, if all 9 cells are occupied, Yangyang rewards Meiyangyang with 10 extra unopened turtle blind boxes.

Since Yangyang only prepared $k$ turtle blind boxes, if the number of blind boxes Meiyangyang obtains reaches $k$ (including the initial $n$ blind boxes), Yangyang will no longer be able to reward Meiyangyang with any blind boxes.

Now, given the sequence of styles of the turtle blind boxes Meiyangyang opens, please determine the quantity of each style of turtle Meiyangyang finally obtains from Yangyang. If Meiyangyang feels she hasn't played enough, please output "Unhappy!" and the number of turtle blind boxes Meiyangyang has left at the end.

Input

The first line contains four integers $n, m, k, t$ ($1 \le n \le k \le 10^5, 1 \le t \le m \le 10^5$), with meanings as described in the problem.

The second line contains $k$ integers $a_1, a_2, \dots, a_k$ ($0 \le a_i \le m$), representing the sequence of styles of the turtle blind boxes Meiyangyang opens.

Output

The first line contains $m+1$ integers, where the $i$-th integer is the number of turtles of style $i-1$ that Meiyangyang finally obtains.

If Meiyangyang feels she hasn't played enough, output "Unhappy!" and the number of turtle blind boxes Meiyangyang has left in the second line.

Examples

Input 1

8 9 16 2
1 0 1 1 2 3 4 5 1 6 1 7 8 9 1 1

Output 1

1 7 1 1 1 1 1 1 1 1

Input 2

2 9 2 1
1 2

Output 2

0 1 1 0 0 0 0 0 0 0
Unhappy! 1