시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB27815113256.652%

문제

바이오리듬(biorhythm)이라는 이론을 들어본 적 있는가? 바이오리듬은 인체에 신체,감성,지성의 세가지 주기가 생년월일의 입력에 따라 어떤 패턴으로 나타나고, 이 패턴의 조합에 따라 능력이나 활동 효율에 차이가 있다는 주장이다.

주헌이는 날마다 달라지는 본인의 코딩 실력도 혹시 바이오리듬의 영향이 아닐까하는 의구심이 들어 수년간의 연구를 진행했다. 그 결과, 코딩과 바이오리듬 사이에 밀접한 연관이 있다는 사실을 발견했고, 주헌이는 이를 코딩 바이오리듬이라는 새로운 개념을 정의하기로 했다. 주헌이가 발견한 코딩 바이오리듬의 값은 생년월일과 날짜를 바탕으로 다음과 같이 계산된다.

'연도'를 $Y(y)$, '월'을 $M(m)$, '일'을 $D(d)$ 의 형식이라고 했을 때, 자신의 생일은 "$YYYY : MM : DD$"로, 자신이 코딩할 날짜는"$yyyy : mm : dd$" 로 정의하고, 편의상       "$Y_1Y_2Y_3Y_4 : M_1M_2 : D_1D_2$", "$y_1y_2y_3y_4 : m_1m_2 : d_1d_2$" 라고 하자. 이때 코딩 바이오리듬의 값은 아래와 공식에 따라 구할 수 있다.

$$\displaystyle \sum_{i=1}^4 {(Y_i-y_i})^2 \times \sum_{j=1}^2 {(M_j-m_j})^2 \times \sum_{k=1}^2 {(D_k-d_k})^2 $$

예를 들어, 자신의 생년월일이 2000년 01월 01일 이고, 코딩할 날짜가 2021년 10월 30일 일 때 코딩 바이오리듬의 값은 아래와 공식에 따라 계산된다.

$Y_1Y_2Y_3Y_4 : M_1M_2 : D_1D_2 = 2000 : 01 : 01$

$y_1y_2y_3y_4 : m_1m_2 : d_1d_2 = 2021 : 10 : 30$

코딩 바이오리듬 $=\{(2-2)^2+(0-0)^2+(0-2)^2+(0-1)^2\}  \times \{(0-1)^2+(1-0)^2\} \times \{(0-3)^2+(1-0)^2\} $

$= 5 \times 2 \times 10 = 100$

누군가의 생년월일과 그 사람이 코딩할 N 일의 날짜가 주어질 때, 날짜 중에서 그 사람의 코딩 바이오리듬이 가장 높은 날의 날짜를 출력하여라. 가장 높은 값을 가지는 날짜가 여러 개라면, 그 중에서 가장 빠른 날짜를 출력한다.

입력

첫 번째 줄에 사람의 생년월일이 주어진다.

두 번째 줄에 그 사람이 코딩할 날짜의 일수 N 이 주어진다. ( 2 ≤ N ≤ 1000 )

세 번째 줄부터 이후 개의 줄에 걸쳐서 코딩할 날짜가 주어진다. 코딩할 날짜는 반드시 생년월일 이후임이 보장되며, 같은 날짜가 2개 이상 주어지지 않는다.

모든 날짜 형식은 $YYYYMMDD$ 형태로 주어지며, 1000년 01월 01일부터 9999년 12월 31일까지 태양력상으로 실제로 존재하는 날짜만 입력으로 주어진다. 

출력

입력 받은 코딩할 날짜 중에서 코딩 바이오리듬이 가장 높은 날의 날짜를 $YYYYMMDD$ 형태로 출력한다. 

가장 높은 값을 가지는 날이 여러 개라면, 그 중에서 가장 빠른 날짜를 출력한다.

예제 입력 1

20000101
3
20211030
20211031
20131114

예제 출력 1

20131114

2000년 01월 01일이 생년월일인 사람의 2021년 10월 30일 코딩 바이오리듬은 100, 2021년 10월 31일에는 90, 2013년 11월 14일에는 100 이다.

세 날짜 중 코딩 바이오리듬의 값이 가장 크면서 가장 빠른 날짜는 2013년 11월 14일이다.

예제 입력 2

20301030
2
99991231
20301225

예제 출력 2

99991231