Controlling Companies

Given a table representing shareholdings between companies, each entry \( (i, j, p) \) indicates that company \( i \) owns \( p\% \) of company \( j \). A company \( A \) is said to control a company \( B \) if at least one of the following conditions holds:

1. \( A = B \).
2. Company \( A \) owns more than \( 50\% \) of the shares of company \( B \) directly.
3. Company \( A \) controls some companies \( C_1, C_2, \ldots, C_K \) (with \( K \ge 1 \)) such that the sum of the percentages of \( B \)'s shares owned by these companies, i.e. \( x_1 + x_2 + \cdots + x_K \), is greater than \( 50\% \).

Your task is to compute all pairs \( (h, s) \) indicating that company \( h \) controls company \( s \). There are at most 100 companies.

inputFormat

The first line of input contains an integer \( N \), representing the number of shareholding records. Each of the following \( N \) lines contains three integers: \( i \), \( j \), and \( p \), which indicate that company \( i \) owns \( p\% \) of company \( j \).

outputFormat

Output each pair of companies \( (h, s) \) where company \( h \) controls company \( s \). Each pair should be printed on a separate line as two space-separated integers. The pairs must be output sorted first by \( h \) and then by \( s \).

sample

3
1 2 80
2 3 80
3 1 20

1 1
1 2
1 3
2 2
2 3
3 1
3 3