시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 (추가 시간 없음) 1024 MB 144 77 40 64.516%

문제

재현이는 문제를 풀다가 신기한 연산을 발견했다. 이 연산을 사용하면 홀수 번 등장하는 원소가 단 하나 있는 원소들의 나열에서 그 원소를 빠르게 찾을 수 있다. 예를 들어 수열 (1, 3, 2, 1, 2)에 이 연산을 적용하면 유일하게 한 번만 등장하는 수인 3을 얻을 수 있다.

재현이는 이 연산에 큰 감명을 받고, 이 연산을 사용하는 문제를 반드시 출제하기로 결심했다. 그리고 마침내 출제할 기회가 주어지자, 다음과 같은 문제를 야심차게 내놓았다.

N종류의 알파벳 소문자로 이루어진 M글자의 문자열과 Q개의 구간들이 주어진다. 문자열에서 각각의 구간에 해당하는 부분 문자열을 뽑았을 때, 각 부분 문자열에는 N종류의 알파벳이 전부 등장하며 그중 홀수 번 등장하는 알파벳이 단 한 종류 있음이 보장된다.

이때 각 구간에 대해 해당하는 부분 문자열에서 홀수 번 등장하는 알파벳을 찾는 프로그램을 작성하라.

문제의 데이터를 준비하던 재현이는 구간들은 쉽게 만들 수 있었으나, 이 구간들에 대해 위의 조건을 만족하는 문자열을 도저히 만들 수 없었다. 그래서 재현이는 데이터를 만드는 작업을 또다른 출제진인 당신에게 맡기기로 했다. 재현이를 도와서 데이터를 만들어 주자.

입력

첫 줄에 세 개의 정수 N, M, Q가 주어진다. N은 사용해야 하는 알파벳의 종류 수, M은 만들고자 하는 문자열의 길이, Q는 재현이가 만들어 놓은 구간들의 개수를 의미한다.

이후 Q개의 줄에 걸쳐 구간들이 주어진다. (i + 1)번째 줄에는 두 개의 정수 siei가 공백을 사이에 두고 주어지며, 각각 구간의 시작 위치와 끝 위치를 의미한다. 각 구간의 너비는 2N − 1 이상의 홀수이며, 같은 구간이 여러 번 주어지지 않음이 보장된다.

출력

첫 줄에 알파벳 소문자만으로 이루어진 M글자의 문자열을 출력한다. 이 문자열은 정확히 N종류의 알파벳으로 이루어져 있어야 하며, 입력으로 주어진 모든 구간에 대해 재현이가 출제하려는 문제의 조건을 만족해야 한다.

이러한 문자열이 존재하는 경우만이 입력으로 주어짐이 보장된다.

제한

  • 1 ≤ N ≤ 26
  • 2N − 1 ≤ M ≤ 100,000
  • 1 ≤ Q ≤ 100,000

예제 입력 1

3 10 4
1 9
3 7
2 6
4 10

예제 출력 1

baccbabbac

첫 번째 구간 [1, 9]에 해당하는 부분 문자열은 baccbabba으로, 알파벳 a가 홀수 번 등장한다.

만약 구간으로 [4, 8]이 주어진다면 cbabb에는 모든 알파벳이 홀수 번 등장하므로 이 문자열은 답이 될 수 없다.

만약 구간으로 [5, 9]가 주어진다면 babba에는 알파벳이 두 종류밖에 사용되지 않았으므로 이 문자열은 답이 될 수 없다.