Recently, Keenan has been thinking about some very interesting questions. Unfortunately, searching them on the internet hasn't been very useful. Instead, Keenan has started to direct his inquiries to various university professors by email. Keenan has received so many responses that he needs to start keeping track of what questions he has asked from each professor, as well as rate the quality of their responses.

Keenan has ~N~ questions and has emailed ~M~ professors so far. Each professor has responded to all of the questions that Keenan has asked, and Keenan has assigned each answer a certain score. Keenan has given you a list of emails that he has sent as well as his score for each of the responses. To make it easier to create the ratings, all values, including the identity of the professor are recorded with positive integers.

Can you help him find the identity of the professor who responded the best to each question?

Constraints

~1 \leq N, M, K \leq 2 \times 10^5~

~1 \leq A \leq M~

~1 \leq B \leq N~

~1 \leq C \leq 100~

Subtask 1 [30%]

~1 \le N, M, K \le 10^3~

Subtask 2 [70%]

No additional constraints.

Input Specification

The first line of input will contain 3 space separated integers, ~N~, ~M~, ~K~. ~N~ represents the number of questions Keenan has, ~M~ represents the number of professors he knows and ~K~ represents the number of emails Keenan has sent.

The next ~K~ lines will each consist of 3 space separated integers: ~A~, ~B~, ~C~. ~A~ represents the professor that Keenan emailed, ~B~ represents the question that Keenan asked and ~C~ represents the score Keenan gave the answer.

Output Specification

The output will consist of ~N~ space separated integers, the ~i~th integer should represent the identity of the professor that best answered the ~i~th problem. If no professor answered a problem, output -1 instead. If two professors had the same score answer, output the one that answered first (the one that appeared earlier in the input).

Sample Input

5 5 4
1 3 4
2 3 9
1 4 1
5 1 10

Sample Output

5 -1 2 1 -1

Explanation

Keenan asked ~1~ professor for the answer to question ~1~, which was professor ~5~. Keenan gave this answer a score of ~10~. This is the best (and only) score, so professor ~5~ answered best for question ~1~.

Keenan didn't ask any professor about question ~2~.

Keenan asked ~2~ professors about question ~3~. Professor ~1~ gave an answer that was rated ~4~ and Professor ~2~ gave an answer that was rated ~9~. Professor ~2~ had the highest score, so he answered best.

Keenan asked ~1~ professor about question ~4~, Professor ~1~ gave the one and only answer with a rating of ~1~. Therefore, professor ~1~ gave the best answer.

Keenan didn't ask any professor about question ~5~.