스키맥싱

Abdullah가 경쟁 프로그래밍 외에 삶에서 열정을 쏟는 것은 스키 경기이다. 하지만 날씨가 점점 더 예측하기 어려워짐에 따라 기후 변화가 자신의 스키 선수 경력에 미칠 영향을 걱정하고 있다. 기온이 높아지면 눈이 더 많이 녹으며, 이는 고도가 높은 산보다 고도가 낮은 산에 더 큰 영향을 미친다.

스키 난이도는 쉬운 것부터 어려운 것 순으로 Green, Blue, Red, Black, DoubleBlack의 다섯 단계이다. 각 산에는 고유한 이름과 고도, 난이도가 있다.

Abdullah는 매년 산 $k$곳에서만 스키를 탈 수 있다. 스키 선수인 그는 이용 가능한 산 중 가장 어려운 $k$곳에서 스키를 타고 싶어 한다. 그는 산의 순위를 난이도에 따라 정하고(어려울수록 좋다), 난이도가 같으면 고도에 따라 정한다(높을수록 좋다).

Abdullah에게는 개인적으로 가장 좋아하는 산도 있으며, 이 산이 반드시 순위가 가장 높은 것은 아니다. 시간제로 점을 보는 Ryan은 어떤 해에 고도가 $x$보다 엄격히 작은 모든 산에서 스키를 탈 수 없을 것이라고 예측한다. 각 해의 예측은 서로 독립적이다. 이 정보가 주어질 때, 매년 Abdullah가 자신이 가장 좋아하는 산에서 스키를 탈지 Ryan이 알려 줄 수 있도록 도와주자.

채점

제출한 프로그램은 여러 테스트 그룹으로 이루어진 테스트 세트로 평가된다. 한 그룹의 점수를 얻으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 점수 | 제약 조건

$1$ |$30$| $m, y \leq 1000$

$2$ |$70$| 추가 제약 조건 없음.

첫째 줄에 세 정수 $k$, $m$, $y$가 주어진다. ($1 \leq k \leq m \leq 2 \cdot 10^5$, $1 \leq y \leq 2 \cdot 10^5$) 여기서 $k$는 Abdullah가 매년 스키를 타는 산의 수, $m$는 전체 산의 수, $y$는 연수이다.

다음 $m$개의 줄에는 각각 문자열 $n_i$ ($1 \leq |n_i| \leq 20$), 정수 $a_i$ ($1 \leq a_i \leq 10^9$), 문자열 $d_i$가 주어지며, 이는 각각 $i$번째 산의 이름, 고도, 난이도이다. 이름은 영숫자로 이루어진다. 난이도는 Green, Blue, Red, Black, DoubleBlack 중 하나이다.

다음 줄에는 Abdullah가 가장 좋아하는 산의 이름인 문자열 $f$가 주어진다. $f$는 $m$개의 산 이름 중 하나임이 보장된다.

다음 $y$개의 줄에는 각각 정수 $x_j$가 주어진다. ($0 \leq x_j \leq 10^9$) $j$년에 고도가 $x_j$보다 엄격히 작은 모든 산은 이용할 수 없다.

모든 산의 이름은 서로 다르다. 난이도와 고도가 모두 같은 두 산은 없다. 각 해에 적어도 $k$개의 산을 이용할 수 있음이 보장된다.

각 해마다 Abdullah가 그해 자신이 가장 좋아하는 산에서 스키를 탄다면 YES를, 그렇지 않다면 NO을 출력한다.

예제 1에서 Abdullah에게는 산이 $3$곳 있다. Titlis (Blue, $3238$), Jungfrau (Blue, $4158$), MontBlanc (Green, $4808$)이다. 그는 가장 어려운 산 두 곳에서 스키를 타고 싶어 한다. 산은 난이도에 따라(Green < Blue < Red < Black < DoubleBlack), 그다음 고도에 따라(높을수록 좋다) 순위가 정해진다.

순위는 다음과 같다.

• Jungfrau (Blue, $4158$)

• Titlis (Blue, $3238$)

• MontBlanc (Green, $4808$)

$1$년에는 ($x=2000$) 모든 산을 이용할 수 있다. 가장 어려운 산 두 곳은 {Jungfrau, Titlis}이다. 그가 가장 좋아하는 Titlis가 이 집합에 포함되므로 답은 YES이다.

$2$년에는 ($x=3500$) Titlis의 고도 ($3238$)가 $3500$보다 작으므로 이용할 수 없다. 이용할 수 있는 산은 {Jungfrau, MontBlanc}뿐이므로 Abdullah는 두 산 모두에서 스키를 탄다. Titlis는 그 안에 없으므로 답은 NO이다.

예제 2에서 Abdullah에게는 산이 두 곳 있다. Matterhorn (DoubleBlack, $4478$)과 Eiger (Red, $3967$)이다. 그는 가장 어려운 산에서 스키를 타고 싶어 한다. 순위는 다음과 같다.

• Matterhorn (DoubleBlack, $4478$)

• Eiger (Red, $3967$)

Abdullah가 가장 좋아하는 산은 Matterhorn이다. 모든 해에 ($x=0, 3967, 4478$) Matterhorn을 이용할 수 있고 가장 어려운 산이므로, $3$개의 모든 질의에 대한 답은 YES이다.