Marisa vừa được ban tổ chức UWU Coding Cup nhờ làm người phụ trách tính điểm cho giải đấu năm nay. Tuy nhiên, sau vài phút nhìn bảng xếp hạng cùng hàng đống luật tính điểm, cô nhận ra mình hoàn toàn không có ý định ngồi cộng tay cho hàng chục nghìn thí sinh.
Vì vậy Marisa quyết định nhờ bạn viết chương trình tính điểm thay cô.

Sau mỗi vòng thi, thí sinh sẽ nhận điểm dựa trên thứ hạng của mình theo bảng sau:

Các thí sinh đứng ngoài top 10 nhận 0 điểm.

Nếu nhiều thí sinh đồng hạng, tất cả sẽ nhận số điểm bằng trung bình cộng điểm của các hạng tương ứng, sau đó làm tròn lên.

Ví dụ: nếu 3 thí sinh cùng đứng hạng 2 thì họ chiếm các vị trí 2,3,4 và cùng nhận:

\(\lceil \frac{75 + 60 + 50}{3} \rceil = 62\) điểm.

Ngoài ra:

- Nếu thí sinh tham dự trực tiếp (on-site), họ nhận thêm 1 điểm thưởng.
- Nếu thí sinh không tham dự, họ nhận 0 điểm thưởng.

Thứ hạng được xác định theo luật ACM với thứ tự ưu tiên:

1. Số bài giải được nhiều hơn → xếp cao hơn
2. Nếu bằng nhau, tổng thời gian phạt ít hơn → xếp cao hơn
3. Nếu vẫn bằng nhau, thời điểm nộp AC cuối cùng sớm hơn → xếp cao hơn

Nếu cả ba giá trị đều bằng nhau thì các thí sinh được xem là đồng hạng.

Nhiệm vụ của bạn là tính số điểm cuối cùng của từng thí sinh.

Input

• Dòng đầu chứa số nguyên \(N\) (\(1 \le N \le 10^5\)) — số thí sinh.
• \(N\) dòng tiếp theo, mỗi dòng gồm bốn số nguyên \(p , t , l , e\):
  • \(p\) (\(0 \le p \le 100\)) — số bài giải được
  • \(t\) (\(0 \le t \le 10^6\)) — tổng thời gian phạt
  • \(l\) (\(0 \le l \le 10^6\)) — thời điểm AC cuối cùng
  • \(e\) (\(e \in \{0, 1\}\)) — có tham dự on-site hay không

Output

In ra \(N\) dòng, dòng thứ \(i\) là số điểm của thí sinh thứ \(i\) theo đúng thứ tự đầu vào.

Example

8
5 200 80 1
5 200 80 0
5 250 100 1
4 150 70 1
4 150 70 0
3 100 50 1
2 90 40 0
1 30 30 1

89
88
61
48
47
41
36
33

12
7 100 50 1
6 120 70 1
6 120 70 0
6 150 80 1
5 200 120 0
5 200 120 1
4 220 140 1
3 300 180 0
2 400 250 1
1 500 400 0
0 0 0 1
0 0 0 0

101
69
68
51
44
45
37
32
30
26
1
0