최적화된 치팅

Bob이 즐기는 게임에 캐릭터의 힘을 크게 높이는 한정 기간 아이템이 나왔다. Bob은 이 아이템을 살 만큼의 인게임 재화를 모을 시간이 없다. 그래서 인터넷에서 찾은 치트 도구로 재화 값을 바꾸려고 한다.

치트 도구는 Bob이 고른 두 값 $x$와 $y$를 받아, 값이 $x$인 메모리 칸을 모두 $y$로 덮어쓴다. Bob은 도구를 안전하게 쓰고 싶다. 재화를 저장한 칸 말고 다른 칸이 바뀌면 게임이 충돌할 수 있기 때문이다. 따라서 도구를 실행하기 전에 재화 값이 메모리 안에서 유일해야 한다.

Bob은 미션 수행이나 아이템 구매처럼 게임이 제공하는 연산으로 재화를 바꿀 수 있다. 연산은 재화 값에 상수를 더하거나, 빼거나, 곱하거나, 나눈다. 연산은 재화 값만 바꾸고 다른 메모리 칸에는 영향을 주지 않는다. 재화가 음수가 되는 연산은 적용할 수 없다. 예를 들어 가진 재화보다 비싼 아이템은 살 수 없다.

게임 메모리는 정수 $n$개로 이루어진 배열이다. Bob은 재화를 저장한 칸의 위치는 알지만, 안전하게 도구를 쓸 수 있도록 재화를 가장 빨리 바꾸는 방법은 모른다. 그 방법을 찾아 달라.

첫째 줄에 세 정수 $n$, $m$, $k$가 주어진다 ($1 \le n \le 10^4$, $1 \le m \le 1000$, $1 \le k \le n$). $n$은 메모리 칸의 수, $m$은 Bob이 쓸 수 있는 연산의 수, $k$는 재화를 저장한 칸의 1부터 시작하는 번호이다.

다음 $n$개 줄에는 메모리 칸에 저장된 값이 순서대로 한 줄에 하나씩 주어진다. 각 값은 1 이상 $10^9$ 이하의 정수이다.

다음 $m$개 줄에는 문자 $p$ (+, -, *, / 중 하나)와 정수 $v$ ($1 \le v \le 10^9$)가 주어진다. 재화 값이 $u$일 때 이 연산을 적용하면 재화 값은 $u$ $p$ $v$가 된다. 예를 들어 + 3은 재화 값을 3 늘린다. 나눗셈은 정수 나눗셈이다 ($7 / 3 = 2$). 결과가 음수가 되는 연산은 적용할 수 없다. 각 연산은 0번을 포함해 여러 번 적용할 수 있다.

재화 값을 메모리 안에서 유일하게 만들 수 있으면, 첫째 줄에 필요한 최소 연산 횟수 $t$를 출력한다. 이어서 $t$개의 줄에 Bob이 적용해야 할 연산의 1부터 시작하는 번호를 순서대로 한 줄에 하나씩 출력한다. 가능한 방법이 여러 개면 그중 아무거나 출력해도 된다.

재화 값을 유일하게 만들 수 없으면 $-1$을 출력한다.