Informatica Online Judge

  철수의 컴퓨터 [2392 / 0958]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 3   Total Tried : 3


The Champion of this Problem (C++) : gs18081 - ms / 1806byte
My Best Submission (C++) : N/A

[35th 지병찬(gs17113)]
Writer ID : [gs17113]

Background

철수의 컴퓨터는 주인을 닮아서, 몰래 폴더 안에 있는 자료를 마음대로 옮겨놓고는 한다.

철수의 프라이버시는 소중하기 때문에, 이를 지켜내기 위해 직접 파일을 원래대로 옮기는 프로그램을 작성했다.

컴퓨터에는 N개의 폴더가 있으며, 각 폴더에는 1부터 N까지 번호가 매겨져 있다.

1번 폴더를 제외한 모든 폴더는 1번 폴더 안에 포함된다. (즉, 폴더가 이루는 트리의 루트는 1번 폴더이다.)

또한, 프로그램이 파일을 옮길때는 자신을 직접 포함한 폴더나 자신이 직접 포함한 폴더로만 옮길 수 있다.

프로그램은 시간을 절약하기 위해 언제나 가장 적게 이동하여 파일을 옮기지만, 굉장히 빠르기에 이에 들어가는 시간은 무시해도 된다.

이 컴퓨터에는 매일 폴더마다 수정시각을 저장해두는데, 파일을 옮기는 경우에는 수정한 것으로 판단한다.

수정 시각은 00:00부터 23:59이며, 그날 하루동안 수정되지 않은 폴더의 수정시각은 00:00이다.

철수의 컴퓨터의 폴더에 관한 정보와, 어떤 시각에 어디서 어디로 파일을 옮겼는지 입력되었을 때,

모든 폴더의 수정시각을 출력하여라.

Input

첫번째 줄에는 폴더의 개수 N이 입력된다

그 다음에는 N줄에 걸쳐 i번째 줄에 i번째 폴더에 직접 포함된 폴더의 개수 M과, 포함된 폴더의 번호들이 공백으로 구분되어 입력된다.

그 다음에는 파일을 옮긴 횟수 T가 입력된다.

그 다음에는 T줄에 걸쳐 시간과 파일을 옮기기 시작하는 폴더와 끝내는 폴더의 번호가 입력된다.(시간은 정렬된채 입력된다)

[입력값의 정의역]

1 <= N, T <= 100,000

Output

N줄에 걸쳐 i번째 줄에 i번 폴더의 수정시각을 출력한다. (시각은 입력된 그대로 출력해야한다)

IO Example

입력1

3
2 2 3
0
0
2
01:00 1 3
12:01 2 1

출력1

12:01
12:01
01:00

입력2

16
4 5 16 7 2
3 6 3 13
1 4
0
2 10 12
0
1 9
1 14
2 15 8
1 11
0
0
0
0
0
0
20
01:27 4 12
01:48 13 10
02:36 3 1
02:41 9 6
02:52 5 16
04:01 2 1
05:59 9 7
06:11 8 2
06:16 9 15
08:33 14 3
10:17 7 13
12:05 10 10
13:01 11 5
13:10 9 10
15:40 15 10
16:51 6 4
19:01 6 8
19:38 13 14
20:27 1 16
23:15 11 15

출력2

23:15
19:38
16:51
16:51
23:15
19:01
23:15
19:38
23:15
23:15
23:15
01:27
19:38
19:38
23:15
20:27

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]