marukaite

타로는 초등학생이고, 전단지 뒷면에 낙서를 하고 있다. 어느 날 타로는 다음과 같은 게임을 떠올렸다.

• n×n 격자 모양의 칸을 그려 둔다.
• 각 칸의 초기 상태는 동그라미가 그려져 있거나 그려져 있지 않거나 둘 중 하나다.
• 이 동그라미를 지우거나 그려서, 최종적으로 어떤 열을 봐도 반드시 동그라미가 정확히 1개만 있고, 어떤 행을 봐도 반드시 동그라미가 1개만 있도록 만드는 것이 목표이며, 이 상태로 만들면 게임을 클리어한 것이다.

타로는 이 게임을 떠올렸지만, 이 게임을 클리어하는 데 시간이 매우 오래 걸린다. 그래서 대학생인 당신에게 도움을 청했다. 타로의 형이며 대학생인 당신의 일은 다음과 같다. 엄밀한 상황을 생각하기 위해, 어떤 칸에 동그라미를 그리는 비용, 어떤 칸에 있는 동그라미를 지우는 비용을 당신은 알아냈다. 이 비용을 사용해 이 게임을 클리어하는 데 드는 조작 비용을 최소화하는 순서를 생각한다. 이때, 최소 비용과 그 비용을 달성하는 순서를 출력하는 프로그램을 작성하시오. 출력에 대해서는, 최소 비용을 달성하는 순서라면 어떤 조작, 순서든 출력해도 된다.

n
W11 W12 .. W1n
W21 W22 .. W2n
..
Wn1 Wn2 .. Wnn
E11 E12 .. E1n
E21 E22 .. E2n
..
En1 En2 .. Enn
F1(n글자)
F2(n글자)
..
Fn(n글자)

• n은 타로가 만든 격자가 한 변에 몇 칸인지를 나타낸다

• Wij는 위에서 i번째, 왼쪽에서 j번째 칸에 동그라미를 그리는 비용을 나타낸다

• Eij는 위에서 i번째, 왼쪽에서 j번째 칸에 그려져 있는 동그라미를 지우는 비용을 나타낸다

• Fi는 위에서 i번째 행의 칸의 초기 상태를 나타낸다

• Fi의 왼쪽에서 j번째 문자에 대해

  • 'o'일 때, 위에서 i번째, 왼쪽에서 j번째 칸에 동그라미가 그려져 있음을 나타낸다.
  • '.'일 때, 위에서 i번째, 왼쪽에서 j번째 칸이 비어 있음을 나타낸다.

mincost
cnt
R1 C1 operate1
R2 C2 operate2
..
Rcnt Ccnt operatecnt

• mincost는 타로의 게임을 클리어하는 데 필요한 최소 비용을 나타낸다.

• mincost는 쓰기 조작, 지우기 조작에서 발생하는 비용의 총합으로 계산된다.

• cnt : mincost의 비용을 달성하는 조작을 한 횟수를 나타낸다

• k번째 (1≤k≤cnt)에 실행하는 조작은 k+2번째 줄에 기술한다

• k번째 (1≤k≤cnt) 조작에 대해

  • 위에서 i번째 칸, 왼쪽에서 j번째 칸에 대해 한 것이라고 하면
  • Rkk이다.
  • 이 조작이 동그라미를 지우는 조작이라면 operatek = "erase"로 하라
  • 이 조작이 동그라미를 그리는 조작이라면 operatek = "write"로 하라
  • Rk,Ck,operatek는 한 줄에 공백으로 구분해 출력해야 한다

• 동그라미가 그려져 있는 칸에 동그라미를 그리는 조작, 그리고 동그라미가 그려져 있지 않은 칸에 동그라미를 지우는 조작을 하면 WrongAnswer이다

• cnt개 조작에 드는 비용의 총합이 mincost와 일치하지 않으면 WrongAnswer이다

• 1≤ n ≤ 100
• 1≤ Wij ≤ 1000
• 1≤ Eij ≤ 1000
• Fi는 문자열이고, 길이는 n이다
• Fi는 'o'와 '.'만으로 구성된다