Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
Jenny's First Exam
Time Limit: 6000MSMemory Limit: 65536K
Total Submissions: 1110Accepted: 259
Case Time Limit: 2000MS

Description

First exams cause many problems to Jenny. One problem is that Jenny needs the whole day to prepare for any exam (good news is she needs only one day for any preparation). Another problem: in a day of the exam Jenny is not able to study anything. And the main problem: Jenny must prepare for i-th exam not earlier then ti days before it, in the other case she forgets absolutely everything by the time of the exam.

Jenny wants to start preparations as later as possible but she has to pass all exams. Help Jenny to choose a day when she must start.

Input

The first line of the input file contains n (1 ≤ n ≤ 50 000) — the number of exams. The following lines describes exams.

Each description consists of three lines. The first line is the name of the subject (a string containing only Latin letters, maximal length is 10). The second line is the date of the exam in format dd.mm.yyyy. The third line contains ti for this exam (1 ≤ ti ≤ 100 000).

All exams take place in interval from 01.01.1900 to 31.12.2100.

Recall that if the year is divisible by 4 and is not divisible by 100, or is divisible by 400 — it is the leap one. Such year has 366 days, the additional day is on February 29.

Output

Output the latest date when Jenny may start preparation and pass all exams. Write date in format dd.mm.yyyy. If it is impossible to pass all the exams, output the word “Impossible”.

Sample Input

sample input #1
3
Philosophy
01.01.1900
1
Algebra
02.01.1900
3
Physics
04.01.1900
10

sample input #2
2
Philosophy
29.06.2005
1
Algebra
30.06.2005
2

Sample Output

sample output #1
30.12.1899

sample output #2
Impossible

Source

Northeastern Europe 2005, Northern Subregion

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator