Cubes Without Holes

Time Limit : 1 sec, Memory Limit : 65536 KB

Problem B: Cubes Without Holes

n × n × n 個の小さい立方体を積み重ね、1つの大きい立方体を作る。さらに、大きい立方体の表面となっているいくつかの小さい立方体の表面に印をつける。n = 4 の例を下図(左)に示す。



次に、上図(右)に示すように、印のついた表面から、反対の面まで水平または垂直に貫通する穴をあける。

あなたの仕事は、n と 印の位置を読み込み、穴の空いていない小さい立方体の個数を数えるプログラムを作成することである。

Input

入力はいくつかのデータセットからなる。各データセットは以下の形式で与えられる:

n h
c1 a1 b1
c2 a2 b2
   .
   .
   .
ch ah bh

h は印の数を示す整数である。これに続く h 行によって h 個の印の位置が入力される。印の位置を指定するために下図に示す座標軸を用いることにする。(x, y, z) = (1, 1, 1) が左下奥の立方体、(x, y, z) = (n, n, n) が右上手前の立方体を示す。



cii 番目の印がつけられている平面を示す文字列である。ci は "xy" 、"xz"、 "yz" のいづれかであり、それぞれ i 番目の印が xy 平面、xz 平面、 yz 平面上にあることを示す。

ai, bi は ci で示された平面上の座標を示す。 xy 平面、xz 平面、yz 平面のとき、ai, bi はそれぞれ平面の座標 (x, y)、(x, z)、(y, z) を示す。例えば、上図において、印 A, B, C の ci, ai, bi の値はそれぞれ、"xy 4 4", "xz 1 2", "yz 2 3" となる。

n, h がともに 0 のとき、入力の終わりを示す。

n ≤ 500, h ≤ 200 と仮定してよい。

Output

各データセットに対して、穴の空いていない立方体の数を1行に出力せよ。

Sample Input

4 3
xy 4 4
xz 1 2
yz 2 3
4 5
xy 1 1
xy 3 3
xz 3 3
yz 2 1
yz 3 3
0 0

Output for the Sample Input

52
46

Source: University of Aizu, ACM-ICPC Japan Domestic Contest 2009 Warm Up I , Aizu-Wakamatsu, Japan, 2009-05-16
Problem Setter:  Yutaka Watanobe