Drawing Lots

Natsume loves big cats. Natsume decided to head to a corner of the schoolyard where stray cats always gather in order to brush the stray cats, which is a daily routine today.

N cats gathered at the spot today. Natsume wanted to brush everyone, but suddenly she was able to do something just before she came there, and she could only brush one in time. Every cat is looking forward to brushing, so if you do only one cat, the other cats will be jealous. So, in order to convince the cats, I decided to decide which cat to brush with Amidakuji.

Amidakuji consists of n vertical lines and m pre-drawn horizontal lines. The horizontal line must connect two adjacent vertical lines so that they are perpendicular to them. Also, horizontal lines must not share endpoints. There is a hit mark at the bottom of one vertical line. An example of Amidakuji that meets these conditions is shown in the figure (these correspond to the sample input example).

Diagram of Amidakuji given in the sample input example Figure: Example of Amidakuji that meets the condition of the problem

Each cat chooses one from the top of the vertical line. And as a result of following the Amidakuji, the rule is that the winning cat can get the right to brush today. Natsume immediately created the Amidakuji. Vertical lines, horizontal lines, and hits were written and hidden so that the horizontal lines could not be seen.

When it was time for the cats to choose, Natsume noticed that among the n cats, there was a stray cat, Actagawa, who normally does not show his face. Actagawa hasn't brushed for another month and his hair is stiff.

Natsume feels sorry for the other cats, but decides to cheat and brush the Actagawa. First, ask the cats to choose the vertical line as usual. When everyone has finished choosing, Natsume secretly adds some horizontal lines and changes the ghost leg so that Actagawa hits.

However, depending on the vertical lines chosen by Actagawa, there are too many horizontal lines to draw in order to hit Actagawa, and the cats may lose their plans while working. Therefore, Natsume first decided to find out how many horizontal lines should be drawn for each vertical line if Actagawa chose it.

In addition, the newly drawn horizontal line must also connect two adjacent vertical lines perpendicularly to them, and must be drawn so that the horizontal lines do not share the end points.

Notes on Submission

Multiple datasets are given in the above format. The first line of input data gives the number of datasets. Create a program that outputs the output for each data set in order in the above format.

Input

Input data is given in the following format.

n m k h1 x1 h2 x2 ... hm xm

The number of vertical lines n (1 ≤ n ≤ 100000), the number of horizontal lines already drawn m (0 ≤ m ≤ 100000), and the number of vertical lines per k (1 ≤ k ≤ n) on the first line of the input Is given. Here, the numbers of the vertical lines are 1, 2, ..., n in order from the left.

The following m lines are given horizontal line information. Each line is given two integers h (1 ≤ h ≤ 1000000) and x (1 ≤ x ≤ n -1) that represent the information of one horizontal line. h is the distance from the lower end of the vertical line, and x is the number of the vertical line on the left side of the vertical lines connected by the horizontal line. In other words, this horizontal line connects the xth and x + 1th vertical lines.

In the input, the horizontal line exists only at the position of the integer height, but the position of the newly added horizontal bar does not necessarily have to be the position of the integer height.

Output

Output an n-line string. On the i (1 ≤ i ≤ n) line, output the minimum number of horizontal lines that must be added to hit the actor when the actor chooses the i-th vertical line.

Example

Input

4 3 2 1 20 1 10 2 5 7 3 70 1 60 4 50 2 40 4 30 1 20 3 10 2 1 0 1 4 2 1 10 1 10 3

Output

1 0 1 1 0 1 1 2 0 1 0 1 2

inputFormat

input example).

Diagram of Amidakuji given in the sample input example Figure: Example of Amidakuji that meets the condition of the problem

Each cat chooses one from the top of the vertical line. And as a result of following the Amidakuji, the rule is that the winning cat can get the right to brush today. Natsume immediately created the Amidakuji. Vertical lines, horizontal lines, and hits were written and hidden so that the horizontal lines could not be seen.

When it was time for the cats to choose, Natsume noticed that among the n cats, there was a stray cat, Actagawa, who normally does not show his face. Actagawa hasn't brushed for another month and his hair is stiff.

Natsume feels sorry for the other cats, but decides to cheat and brush the Actagawa. First, ask the cats to choose the vertical line as usual. When everyone has finished choosing, Natsume secretly adds some horizontal lines and changes the ghost leg so that Actagawa hits.

However, depending on the vertical lines chosen by Actagawa, there are too many horizontal lines to draw in order to hit Actagawa, and the cats may lose their plans while working. Therefore, Natsume first decided to find out how many horizontal lines should be drawn for each vertical line if Actagawa chose it.

In addition, the newly drawn horizontal line must also connect two adjacent vertical lines perpendicularly to them, and must be drawn so that the horizontal lines do not share the end points.

Notes on Submission

Multiple datasets are given in the above format. The first line of input data gives the number of datasets. Create a program that

outputFormat

outputs the output for each data set in order in the above format.

Input

Input data is given in the following format.

n m k h1 x1 h2 x2 ... hm xm

The number of vertical lines n (1 ≤ n ≤ 100000), the number of horizontal lines already drawn m (0 ≤ m ≤ 100000), and the number of vertical lines per k (1 ≤ k ≤ n) on the first line of the input Is given. Here, the numbers of the vertical lines are 1, 2, ..., n in order from the left.

The following m lines are given horizontal line information. Each line is given two integers h (1 ≤ h ≤ 1000000) and x (1 ≤ x ≤ n -1) that represent the information of one horizontal line. h is the distance from the lower end of the vertical line, and x is the number of the vertical line on the left side of the vertical lines connected by the horizontal line. In other words, this horizontal line connects the xth and x + 1th vertical lines.

In the input, the horizontal line exists only at the position of the integer height, but the position of the newly added horizontal bar does not necessarily have to be the position of the integer height.

Output

Output an n-line string. On the i (1 ≤ i ≤ n) line, output the minimum number of horizontal lines that must be added to hit the actor when the actor chooses the i-th vertical line.

Example

Input

4 3 2 1 20 1 10 2 5 7 3 70 1 60 4 50 2 40 4 30 1 20 3 10 2 1 0 1 4 2 1 10 1 10 3

Output

1 0 1 1 0 1 1 2 0 1 0 1 2

样例

4
3 2 1
20 1
10 2
5 7 3
70 1
60 4
50 2
40 4
30 1
20 3
10 2
1 0 1
4 2 1
10 1
10 3

1
0
1
1
0
1
1
2
0
1
0
1
2

</p>