Nam năm nay lên \(7\) tuổi và bước vào lớp \(1\). Nam tự hỏi nếu khi mình \(X\) tuổi thì Nam sẽ học lớp mấy. Nếu Nam chưa đủ tuổi vào lớp \(1\), in ra "Chua di hoc". Nếu Nam đã quá tuổi học lớp 12, in ra "Da tot nghiep". Nếu Nam ở độ tuổi học từ lớp \(1\) đến lớp \(12\), in ra "Lop \(A\)" với \(A\) là lớp Nam học khi \(X\) tuổi.

Input

• Dòng duy nhất chứa 1 số nguyên dương \(X\) \((1 \leq X \leq 100)\)

Output

• Dòng duy nhất chứa kết quả:

  • Nếu Nam chưa đủ tuổi vào lớp \(1\), in ra "Chua di hoc"
  • Nếu Nam đã quá tuổi học lớp \(12\), in ra "Da tot nghiep"
  • Nếu Nam ở độ tuổi từ lớp \(1\) đến lớp \(12\), in ra "Lop \(A\)", với \(A\) là lớp của Nam.

Example

9

Lop 3

19

Da tot nghiep

6

Chua di hoc

Quýt ngon mỗi quả chia ba

Cam ngon mỗi quả bổ ra làm mười

Mỗi người một miếng chia đều

Bổ mười bảy quả trăm người đủ chia

Hỏi có bao nhiêu quả cam, bao nhiêu quả quýt?

Các câu đố toán dân gian luôn là một chủ đề thú vị với các bạn học sinh. Hôm nay, các bạn sẽ giải phiên bản tổng quát của bài toán này: Tổng số lượng quả là \(n\) và tổng số người là \(p\) (cam vẫn bổ mười và quýt vẫn chia ba). Hỏi có bao nhiêu quả cam, bao nhiêu quả quýt?

Input

• Một dòng duy nhất chứa hai số nguyên dương \(n,p (1 \le n,p \le 1000)\)

Output

• Một dòng duy nhất chứa số quả quýt & quả cam.
• Dữ liệu đảm bảo chia đều được mỗi người một miếng (câu thơ "trăm người đủ chia")

Example

Input 1

17 100

Output 1

10 7

Giải thích:

Có \(10\) quả quýt và \(7\) quả cam, số miếng được cắt ra là \(10\times 3 + 7\times 10 = 100\)

Hôm nay, Nam tìm thấy một hộp diêm cũ trên gác. Vì đang chán, cậu nghĩ ra một trò chơi với các que diêm. Nam rất thích hình chữ nhật, vì vậy cậu muốn xếp các que diêm để tạo thành một hình chữ nhật rỗng (chỉ chứa các cạnh và độ dài các cạnh là số nguyên dương). Trong hộp diêm có \(N\) que diêm, Nam muốn dùng tất cả \(N\) que diêm này để tạo thành được một hình chữ nhật duy nhất. Trong lúc xếp, cậu tự hỏi liệu hình chữ nhật cậu tạo được có thể có diện tích nhỏ nhất và lớn nhất là bao nhiêu? Nam đã tính ra được, tuy vậy đáp số lại quá lớn nên cậu không chắc về đáp án của mình. Bạn hãy lập trình để giúp Nam xem cậu ấy có tính đúng không nhé.

Input

• Dòng duy nhất chứa số nguyên dương \(N\) \((1 \leq N \leq 10^8)\)

Output

• In ra 2 dòng là kết quả của bài toán:

  • Nếu Nam tạo được hình chữ nhật, dòng đầu in ra diện tích nhỏ nhất, dòng thứ hai in ra diện tích lớn nhất.
  • Nếu Nam không tạo được hình chữ nhật, cả 2 dòng đều in ra số \(-1\)

• Với mỗi test, mỗi đáp án đúng bạn sẽ được 50% số điểm của test đó.

Scoring

• \(30\%\) số test ứng với \(1 \leq N \leq 10^3\)
• \(30\%\) số test khác ứng với \(N \leq 10^5\)
• \(40\%\) số test còn lại ứng với \(N \leq 10^8\)

Example

10

4
6

12

5
9

5

-1
-1

Năm 2222, trường tiểu học chuyên L tổ chức thi tuyển sinh vào lớp chuyên tin. Trường dự tính sẽ tuyển vào \(m\) học sinh. Có \(n\) thí sinh tham gia dự thi. Mỗi thí sinh sẽ trải qua 3 môn thi chung (Toán, Văn, Anh) và môn chuyên (Tin). Điểm xét tuyển được tính bằng công thức sau:
\(\(score = T + V + A + 3\times C\)\)

trong đó \(T,V,A,C\) lần lượt là điểm thi các môn Toán, Văn, Anh và môn chuyên.

Cho biết họ tên, điểm thi của \(n\) thí sinh, hãy in ra tên của \(m\) thí sinh trúng tuyển - \(m\) thí sinh có điểm xét tuyển cao nhất.

• Trong trường hợp bạn xếp thứ \(m\) có điểm bằng bạn xếp thứ \(m+1\), trường sẽ chấp nhận tuyển ít hơn \(m\) bạn: loại toàn bộ những bạn bằng điểm với bạn xếp thứ \(m\)

Input

• Dòng đầu tiên chứa hai số nguyên \(n,m (1 \le m \le n \le 1000)\)
• \(n\) dòng tiếp theo, mỗi dòng chứa thông tin về một thí sinh theo khuôn dạng sau
  Tên T V A C

trong đó Tên mỗi bạn đều là các xâu kí tự gồm ba từ. Không bạn nào có tên giống nhau.

• Ngoài ra, \(0 < T,V,A,C \le 10\), đều là các số thực có tối đa 2 chữ số sau dấu thập phân.

Output

• Giả sử có \(k\) bạn trúng tuyển, in ra \(k\) dòng là tên của các bạn trúng tuyển.

Example

Input 1

5 3
Le Ngoc Bac 10 6 9 10
Pham Hong Vu 8 7 10 9
Tran Trieu Tan 8 6 10 9.5
Nguyen Minh Huy 9 5 9.5 8
Vu Vuong Long 10 5 10 10

Output 1

Le Ngoc Bac
Vu Vuong Long
Tran Trieu Tan

Hôm nay, bé được học về toán và hình học cơ bản. Bé nghĩ ra trò chơi như sau:

Trên tam giác, bé ghi \(3\) số nguyên dương \(a,b,c\) ở \(3\) đỉnh.

Sau đó, bé lặp đi lặp lại quá trình sau: Trên ba cạnh của tam giác, bé lần lượt viết trên trung điểm của cạnh đó một số có giá trị bằng tổng của \(2\) số ở \(2\) đầu cạnh đấy. Ba số mới được viết này sẽ tạo được một tam giác mới. Bé cứ tiếp tục lặp lại quá trình trên với tam giác mới tạo được.

Để rõ hơn, em hãy xem hình minh họa với \(a = 1, b = 2, c = 3\) và bé đã thực hiện quá trình trên \(2\) lần:

Bé thắc mắc: sau khi thực hiện quá trình trên \(n\) lần thì tổng ba số trên đỉnh của tam giác vừa mới tạo được bằng bao nhiêu?

Vì tổng có thể rất lớn, hãy in ra kết quả sau khi chia lấy dư cho \(2004010501\)

Input

• Một dòng duy nhất chứa 4 số \(a,b,c,n (1 \le a,b,c \le 100) (1 \le n \le 10^9)\)

Output

• Một dòng duy nhất chứa đáp án (theo modulo \(2004010501\))

Subtask

• \(40\%\) số test có \(n \le 10^4\)
• \(60\%\) số test có \(n \le 10^9\)

Example

Input 1

1 2 3 2

Output 1

24