Random Index Vectors

Random Index Vectors(RIV)는 패턴 매칭에 쓰이는 비교적 새로운 기법이다. RIV는 1과 -1로 이루어진 크고 희소한 벡터다. 무작위로 생성하면 두 RIV의 내적은 0이거나 0에 매우 가까우므로, 서로 직교하거나 거의 직교한다. RIV는 여러 속성에 하나씩 할당한 뒤 특정한 방식으로 결합해 그 속성들을 가진 패턴의 벡터를 만드는 데 쓰인다. 그러면 두 패턴의 벡터 사이 각의 코사인을 두 패턴의 유사도로 사용할 수 있다.

RIV에는 세 가지 기본 연산이 있다.

• 두 RIV를 원소별로 더할 수 있다: Ci = Ai+Bi.
  • RIV의 비영 원소는 1과 -1뿐이므로 1+1=1이고 -1+-1=-1이다.
• 두 RIV를 원소별로 곱할 수 있다: Ci = Ai×Bi.
• 한 RIV를 정수 k만큼 회전할 수 있다. 모든 값을 왼쪽(인덱스가 작아지는 방향)으로 k만큼 옮기고, 벡터 앞쪽에서 밀려난 값은 끝으로 간다.

RIV는 크고 희소하기 때문에 보통 압축된 표현을 쓴다. 벡터는 값이 비영인 위치의 인덱스(1부터 시작)를 정렬한 목록으로 나타내며, 값이 -1이면 그 인덱스에 음수 부호를 붙인다. 표현은 비영 인덱스의 개수로 시작한다.

예를 들어 다음 RIV를 보자.

1 0 -1 0 0 0 -1 0 0 1 0

비영 원소가 인덱스 1, 3, 7, 10에 4개 있다. 압축 표현은 다음과 같다.

4 1 -3 -7 10

압축 표현으로 주어진 두 RIV에 대해 덧셈, 곱셈, 그리고 두 벡터 각각의 회전을 수행하라. 결과 벡터를 압축 형태로 출력하라.

입력은 테스트 케이스 하나로 이루어진다. 프로그램은 서로 다른 입력으로 여러 번 실행될 수 있다.

각 테스트 케이스의 첫 줄에는 공백으로 구분된 두 정수 n (1 ≤ n ≤ 1018)과 k (1 ≤ k ≤ n)가 주어진다. n은 벡터의 최대 인덱스이고, k는 회전할 칸 수다.

다음 두 줄에는 각각 압축 형태의 벡터가 주어진다. 정수 m (0 ≤ m ≤ 1,000)으로 시작하고 그 뒤에 m개의 인덱스 i (1 ≤ |i| ≤ n)가 공백으로 구분되어 이어진다.

네 개의 Random Index Vector를 한 줄에 하나씩 압축 형태로 출력한다.

• 첫째 줄에는 입력 벡터의 합을 출력한다.
• 둘째 줄에는 입력 벡터의 곱을 출력한다.
• 셋째 줄에는 첫 번째 입력 벡터를 k만큼 회전한 결과를 출력한다.
• 넷째 줄에는 두 번째 입력 벡터를 k만큼 회전한 결과를 출력한다.