Chọn engine từ log kiểm thử

Phiên bản: Phước Hưng OJ Extended

Đề bài

Một hệ thống kiểm thử đang đánh giá $n$ engine. Các engine được đánh số từ $1$ đến $n$ theo đúng thứ tự xuất hiện trong dữ liệu vào.

Với engine thứ $i$, hệ thống ghi nhận ba thông số:

• $nodes_i$: số node mà engine đã xét trong quá trình tìm kiếm;
• $correct_i$: số thế chiến thuật mà engine giải đúng;
• $depth_i$: độ sâu tìm kiếm mà engine đã hoàn tất.

Cần chọn ra engine tốt nhất theo thứ tự ưu tiên sau:

1. Engine có số thế giải đúng $correct_i$ lớn hơn được ưu tiên.
2. Nếu hai engine có cùng số thế giải đúng, engine có độ sâu $depth_i$ lớn hơn được ưu tiên.
3. Nếu cả $correct_i$ và $depth_i$ đều bằng nhau, engine có số node đã xét $nodes_i$ nhỏ hơn được ưu tiên.
4. Nếu cả ba thông số trên đều bằng nhau, engine có số thứ tự nhỏ hơn được ưu tiên.

Nói cách khác, việc so sánh luôn được thực hiện lần lượt theo thứ tự:

$$correct\ \text{giảm dần} \rightarrow depth\ \text{giảm dần} \rightarrow nodes\ \text{tăng dần} \rightarrow \text{số thứ tự engine tăng dần}.$$

Hãy xác định engine tốt nhất trong toàn bộ log kiểm thử.

Input

Dòng đầu tiên chứa số nguyên $n$ — số lượng engine.

Trong $n$ dòng tiếp theo, dòng thứ $i$ chứa ba số nguyên:

nodes_i correct_i depth_i

mô tả kết quả kiểm thử của engine thứ $i$, trong đó:

• $nodes_i$ là số node engine thứ $i$ đã xét;
• $correct_i$ là số thế chiến thuật engine thứ $i$ giải đúng;
• $depth_i$ là độ sâu tìm kiếm engine thứ $i$ đã hoàn tất.

Số thứ tự của engine không xuất hiện riêng trong Input. Engine ở dòng dữ liệu đầu tiên được đánh số $1$, engine ở dòng dữ liệu thứ hai được đánh số $2$, và tương tự cho đến engine thứ $n$.

Output

In ra bốn số nguyên:

id correct depth nodes

trong đó:

• $id$ là số thứ tự của engine tốt nhất;
• $correct$ là số thế chiến thuật mà engine đó giải đúng;
• $depth$ là độ sâu tìm kiếm mà engine đó đã hoàn tất;
• $nodes$ là số node mà engine đó đã xét.

Subtask

• Subtask 1 — 15%: $1 \le n \le 100$; $0 \le nodes_i,correct_i,depth_i \le 10^{18}$; các giá trị $correct_i$ đôi một khác nhau.
• Subtask 2 — 20%: $1 \le n \le 5000$; $0 \le nodes_i,correct_i,depth_i \le 10^{18}$; nếu hai engine có cùng $correct_i$ thì chúng luôn có $depth_i$ khác nhau.
• Subtask 3 — 25%: $1 \le n \le 5\cdot10^4$; $0 \le nodes_i,correct_i,depth_i \le 10^{18}$; nếu hai engine có cùng $correct_i$ và $depth_i$ thì chúng luôn có $nodes_i$ khác nhau.
• Subtask 4 — 40%: $1 \le n \le 2\cdot10^5$; $0 \le nodes_i,correct_i,depth_i \le 10^{18}$; không có điều kiện bổ sung.

Ví dụ

Ví dụ 1

Input

3
900000 18 10
500000 19 9
2000000 19 11

Output

3 19 11 2000000

Giải thích

Có ba engine:

• engine $1$: $nodes=900000$, $correct=18$, $depth=10$;
• engine $2$: $nodes=500000$, $correct=19$, $depth=9$;
• engine $3$: $nodes=2000000$, $correct=19$, $depth=11$.

Engine $1$ chỉ giải đúng $18$ thế, trong khi engine $2$ và engine $3$ đều giải đúng $19$ thế, nên engine $1$ không được chọn.

Engine $2$ và engine $3$ có cùng:

$$correct=19.$$

Do đó xét tiếp độ sâu.

Ta có:

$$depth_2=9,\qquad depth_3=11.$$

Vì $11>9$, engine $3$ được ưu tiên.

Số node chỉ được xét khi cả correct và depth đều bằng nhau, vì vậy việc engine $3$ xét nhiều node hơn engine $2$ không làm thay đổi kết quả.

Engine tốt nhất là engine số $3$.

---

Ví dụ 2

Input

4
1000000 25 12
800000 25 12
600000 24 15
900000 25 11

Output

2 25 12 800000

Giải thích

Engine $1$, engine $2$ và engine $4$ cùng giải đúng $25$ thế, nhiều hơn engine $3$ với $24$ thế.

Trong ba engine còn lại:

• engine $1$ có $depth=12$;
• engine $2$ có $depth=12$;
• engine $4$ có $depth=11$.

Do đó engine $4$ bị loại vì có độ sâu nhỏ hơn.

Engine $1$ và engine $2$ cùng có:

$$correct=25,\qquad depth=12.$$

Ta tiếp tục so sánh số node:

$$nodes_1=1000000,\qquad nodes_2=800000.$$

Vì $800000<1000000$, engine $2$ được ưu tiên.

---

Ví dụ 3

Input

4
500000 30 14
500000 30 14
700000 30 14
100000 29 20

Output

1 30 14 500000

Giải thích

Ba engine đầu tiên đều có:

$$correct=30,$$

nên đều được ưu tiên hơn engine $4$, mặc dù engine $4$ đạt độ sâu lớn hơn.

Engine $1$, engine $2$ và engine $3$ tiếp tục có cùng:

$$depth=14.$$

Xét số node:

$$nodes_1=500000,\qquad nodes_2=500000,\qquad nodes_3=700000.$$

Engine $3$ kém ưu tiên hơn vì đã xét nhiều node hơn.

Engine $1$ và engine $2$ vẫn hoàn toàn bằng nhau ở cả ba thông số:

$$correct=30,\qquad depth=14,\qquad nodes=500000.$$

Khi đó sử dụng tiêu chí cuối cùng: engine có số thứ tự nhỏ hơn được ưu tiên.

Vì:

$$1<2,$$

engine $1$ được chọn.

---

Ví dụ 4

Input

1
123456789012345678 1000000000000000000 999999999999999999

Output

1 1000000000000000000 999999999999999999 123456789012345678

Giải thích

Chỉ có một engine nên engine số $1$ chắc chắn là engine tốt nhất.

Ví dụ này cũng cho thấy các thông số có thể rất lớn và có thể đạt tới cỡ $10^{18}$.