대회 이름 정하기

연세대학교와 고려대학교가 매년 벌이는 정기전에는 공식 명칭을 정하는 규칙이 있다. 주최 측 학교를 뒤로 보내서, 연세대가 주최하면 "고연전", 고려대가 주최하면 "연고전"이 공식 명칭이 된다. 그러나 학교와 관계없이 연세대 학생은 "연고전", 고려대 학생은 "고연전"이라고 부르는 것이 일반적이다. 이 대회의 공식 명칭을 정할 때도 각 학교의 운영진은 자기 학교 이름을 앞에 두고 싶어 했다. 결국 다음과 같은 게임으로 이름을 정하기로 했고, 연세대 측 출제자 Y와 고려대 측 출제자 K가 맞붙었다.

$N$장의 카드가 일렬로 놓여 있다. 각 카드에는 '연' 또는 '고'와 $10^9$ 이하의 자연수가 적혀 있다. 가장 왼쪽 카드를 1번, 그다음 카드를 2번, ..., $N$번 카드라고 하자. $l$번부터 $r$번까지의 카드 중에서 몇 장을 골라 순서대로 나열한다. Y는 "연고"가 반복되도록, K는 "고연"이 반복되도록 고른다. 같은 글자가 적힌 카드를 연달아 고를 수 없다. Y는 '연'이 적힌 카드로 시작해서 '고'가 적힌 카드로 끝내고, K는 '고'가 적힌 카드로 시작해서 '연'이 적힌 카드로 끝낸다. 각자 고른 카드에 적힌 수의 합이 그 사람의 점수이며, 점수가 높은 쪽이 이긴다. 조건에 맞게 카드를 고를 수 없으면 점수는 0점이다.

이 게임은 $T$번 진행된다. 매 게임마다 Y와 K가 같은 카드를 고르는 것도 허용된다. Y와 K는 학교의 자존심을 걸고 최선의 전략으로 게임에 임한다. 각 게임에서 승자와 그 점수를 출력하라.

첫째 줄에 카드의 개수 $N$이 주어진다.

둘째 줄에 카드에 적힌 글자가 하나의 문자열로 주어진다. '연'이 적힌 카드는 Y, '고'가 적힌 카드는 K로 표시한다.

셋째 줄에 각 카드에 적힌 자연수 $a_i$가 공백으로 구분되어 주어진다. ($1 \leq i \leq N$)

넷째 줄에 게임의 횟수 $T$가 주어진다.

다섯째 줄부터 $T$줄에 걸쳐 카드를 고를 수 있는 구간 $[l_i, r_i]$이 주어진다. ($1 \leq i \leq T$)

각 게임에서 승자와 그 점수를 공백으로 구분하여 한 줄에 출력한다. 무승부이면 YK와 점수를 공백으로 구분하여 출력한다.

$1 \leq N, T \leq 500\,000$

$1 \leq a_i \leq 10^9$ $(1 \leq i \leq N)$

$1 \leq l_i \leq r_i \leq N$ $(1 \leq i \leq T)$

이 대회의 공식 명칭은 "2023 고려대학교x연세대학교 프로그래밍 경시대회"이다.