점프하는 돌

Jonathan은 강 위에서 악당 Putra the Mad Man과 싸우고 있다. 강에는 왼쪽부터 오른쪽으로 1, 2, ..., N 위치에 N개의 디딤돌이 있다. Jonathan은 이 돌 위에만 설 수 있고, 강에 빠지지 않아야 한다(그는 수영을 잘하지 못한다).

원래 Jonathan은 점프를 잘하지 못한다(이 싸움에서 그는 돌 사이를 점프해야 한다). 그러나 Kathmandu에서 Dr. Effendy에게 신비한 힘을 배운 뒤 모든 것이 바뀌었다. 이제 Jonathan은 필요한 어디로든 점프할 수 있다. 구체적으로, 그는 위치 p의 돌에서 p ≠ q인 위치 q의 돌로 점프할 수 있지만, (|p − q| − 1)2의 신비한 에너지가 필요하다. 예를 들어, p = 10에서 q = 15로 직접 점프하려면 (|10 − 15| − 1)2 = (| − 5| − 1)2 = 42 = 16의 신비한 에너지가 필요하다. 물론 p = 10에서 q = 15로 가려면 신비한 에너지를 아끼기 위해 여러 번 작은 단계로 점프할 수 있다. 예를 들어 10 → 11 → 12 → 13 → 14 → 15는 총 0 + 0 + 0 + 0 + 0 = 0의 신비한 에너지가 필요하다.

한편, 엄청난 육체적 힘 외에도 Putra는 손가락을 튕기는 것만으로 어느 위치에든 돌을 만들거나 없앨 수 있다. 그러나 Putra는 완벽주의자이므로 정수 위치에만 돌을 만들거나 없앨 수 있다. Jonathan은 위치 x에 돌이 있을 때만 위치 x로 점프할 수 있다. 예를 들어 위치 12와 13의 돌이 없어지면 Jonathan은 10 → 11 → 14 → 15로 p = 10에서 q = 15로 갈 수 있고, 총 0 + 4 + 0 = 4의 신비한 에너지가 필요하다.

이 문제에서는 Putra와 싸우는 동안 Jonathan이 움직이는 데 필요한 신비한 에너지를 계산하는 것을 돕는다.

다음과 같은 유형의 Q개의 쿼리가 주어진다.

• add p — Putra가 위치 p에 돌을 만든다,
• rem p — Putra가 위치 p의 돌을 없앤다,
• go p q — 위치 p에서 위치 q로 가는 데 필요한 최소 신비한 에너지를 출력한다. 총 필요한 신비한 에너지가 최소이기만 하면 Jonathan이 여러 번 점프해도 상관없다.

처음에는 위치 1부터 N까지 모든 돌이 있다. 그러나 싸움이 시작될 때 Putra는 이 N개의 돌 중 M개를 없앤다. 다행히 Putra는 두 번째 유형의 쿼리에서 보듯이 싸우는 동안 한 번에 하나의 돌만 없앨 수 있다.

입력은 세 정수 N M Q (1 ≤ N ≤ 109; 0 ≤ M ≤ 50 000; 1 ≤ Q ≤ 50 000)를 포함하는 한 줄로 시작한다. 이는 각각 전체 돌의 수, 싸움 시작 시 Putra가 없앤 돌의 수, 쿼리의 수를 나타낸다. 다음 줄에는 M개의 정수 pi (1 ≤ pi ≤ N)가 엄격히 증가하는 순서로 주어지며, 이는 싸움 시작 시 Putra가 없앤 돌의 위치를 나타낸다. 다음 Q줄에는 각각 다음과 같은 유형의 쿼리가 하나씩 주어진다.

• add p (1 ≤ p ≤ N) — 이 쿼리 직전에 위치 p에 돌이 없음이 보장된다.
• rem p (1 ≤ p ≤ N) — 이 쿼리 직전에 위치 p에 돌이 있음이 보장된다.
• go p q (1 ≤ p, q ≤ N; p ≠ q) — 위치 p와 q 모두에 돌이 있음이 보장된다. 세 번째 유형(go 쿼리)의 쿼리가 적어도 하나 있다.

세 번째 유형의 각 쿼리에 대해 입력 순서대로, 위치 p의 돌에서 위치 q의 돌로 가는 데 필요한 최소 총 신비한 에너지를 나타내는 정수를 한 줄에 출력한다.