import std.conv, std.functional, std.range, std.stdio, std.string; import std.algorithm, std.array, std.bigint, std.bitmanip, std.complex, std.container, std.math, std.mathspecial, std.numeric, std.regex, std.typecons; import core.bitop; class EOFException : Throwable { this() { super("EOF"); } } string[] tokens; string readToken() { for (; tokens.empty; ) { if (stdin.eof) { throw new EOFException; } tokens = readln.split; } auto token = tokens.front; tokens.popFront; return token; } int readInt() { return readToken.to!int; } long readLong() { return readToken.to!long; } real readReal() { return readToken.to!real; } bool chmin(T)(ref T t, in T f) { if (t > f) { t = f; return true; } else { return false; } } bool chmax(T)(ref T t, in T f) { if (t < f) { t = f; return true; } else { return false; } } int binarySearch(alias pred, T)(in T[] as) { int lo = -1, hi = cast(int)(as.length); for (; lo + 1 < hi; ) { const mid = (lo + hi) >> 1; (unaryFun!pred(as[mid]) ? hi : lo) = mid; } return hi; } int lowerBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a >= val)); } int upperBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a > val)); } struct ModInt(uint M_) { import std.conv : to; alias M = M_; uint x; this(ModInt a) { x = a.x; } this(uint x_) { x = x_ % M; } this(ulong x_) { x = cast(uint)(x_ % M); } this(int x_) { x = ((x_ %= cast(int)(M)) < 0) ? (x_ + cast(int)(M)) : x_; } this(long x_) { x = cast(uint)(((x_ %= cast(long)(M)) < 0) ? (x_ + cast(long)(M)) : x_); } ref ModInt opAssign(T)(inout(T) a) if (is(T == uint) || is(T == ulong) || is(T == int) || is(T == long)) { return this = ModInt(a); } ref ModInt opOpAssign(string op, T)(T a) { static if (is(T == ModInt)) { static if (op == "+") { x = ((x += a.x) >= M) ? (x - M) : x; } else static if (op == "-") { x = ((x -= a.x) >= M) ? (x + M) : x; } else static if (op == "*") { x = cast(uint)((cast(ulong)(x) * a.x) % M); } else static if (op == "/") { this *= a.inv(); } else static assert(false); return this; } else static if (op == "^^") { if (a < 0) return this = inv()^^(-a); ModInt b = this, c = 1U; for (long e = a; e; e >>= 1) { if (e & 1) c *= b; b *= b; } return this = c; } else { return mixin("this " ~ op ~ "= ModInt(a)"); } } ModInt inv() const { uint a = M, b = x; int y = 0, z = 1; for (; b; ) { const q = a / b; const c = a - q * b; a = b; b = c; const w = y - cast(int)(q) * z; y = z; z = w; } assert(a == 1); return ModInt(y); } ModInt opUnary(string op)() const { static if (op == "+") { return this; } else static if (op == "-") { ModInt a; a.x = x ? (M - x) : 0U; return a; } else static assert(false); } ModInt opBinary(string op, T)(T a) const { return mixin("ModInt(this) " ~ op ~ "= a"); } ModInt opBinaryRight(string op, T)(T a) const { return mixin("ModInt(a) " ~ op ~ "= this"); } bool opCast(T: bool)() const { return (x != 0U); } string toString() const { return x.to!string; } } enum MO = 998244353; alias Mint = ModInt!MO; void main() { /* debug { foreach (m; 1 .. 8 + 1) foreach (n; 1 .. 8 + 1) if (m <= n) { writefln("m = %s, n = %s", m, n); writeln; const g = gcd(m, n); int cnt; auto a = new int[][](m, n); auto fs = new int[4][m]; auto gs = new int[4][n]; auto ps = new int[4][g]; auto qs = new int[4][g]; bool trivial() { { bool ok = true; foreach (x; 0 .. m) ok = ok && (fs[x][1] == n || fs[x][3] == n); if (ok) return true; } { bool ok = true; foreach (y; 0 .. n) ok = ok && (gs[y][0] == m || gs[y][2] == m); if (ok) return true; } return false; } void dfs(int x, int y) { if (x == m) { ++cnt; if (!trivial) { foreach (xx; 0 .. m) { foreach (yy; 0 .. n) { write("v>^<"[a[xx][yy]]); } writeln; } writeln; } } else if (y == n) { dfs(x + 1, 0); } else { foreach (b; 0 .. 4) { a[x][y] = b; const z = (x + y) % g; const w = (x + (n - y)) % g; ++fs[x][b]; ++gs[y][b]; ++ps[z][b]; ++qs[w][b]; bool ok = true; ok = ok && !(fs[x][1] && fs[x][3]); ok = ok && !(gs[y][0] && gs[y][2]); ok = ok && !(ps[z][0] && ps[z][1]); ok = ok && !(ps[z][2] && ps[z][3]); ok = ok && !(qs[w][0] && qs[w][3]); ok = ok && !(qs[w][2] && qs[w][1]); if (ok) { dfs(x, y + 1); } --fs[x][b]; --gs[y][b]; --ps[z][b]; --qs[w][b]; } } } dfs(0, 0); stderr.writeln(m, " ", n, ": ", cnt); stderr.flush; writeln('-'.repeat(80).array); writeln; stdout.flush; } return; } //*/ try { for (; ; ) { const numCases = readInt; foreach (caseId; 0 .. numCases) { const M = readLong; const N = readLong; const K = readInt; auto X = new long[K]; auto Y = new long[K]; auto D = new long[K]; foreach (k; 0 .. K) { X[k] = readInt; Y[k] = readInt; D[k] = "RULD".indexOf(readToken[0]); } const G = gcd(M, N); debug { writefln("M = %s, N = %s, G = %s", M, N, G); writeln("X = ", X); writeln("Y = ", Y); writeln("D = ", D); } int[long] fs, gs, ps, qs; foreach (k; 0 .. K) { const x = X[k]; const y = Y[k]; const z = (x + y) % G; const w = (x + N - y) % G; if (x !in fs) fs[x] = 0; if (y !in gs) gs[y] = 0; if (z !in ps) ps[z] = 0; if (w !in qs) qs[w] = 0; fs[x] |= 1 << D[k]; gs[y] |= 1 << D[k]; ps[z] |= 1 << D[k]; qs[w] |= 1 << D[k]; } debug { writeln("fs = ", fs); writeln("gs = ", gs); writeln("ps = ", ps); writeln("qs = ", qs); } int all; foreach (k; 0 .. K) { all |= 1 << D[k]; } Mint ans; // trivial each x { bool ok = true; long m = M; foreach (x, f; fs) { ok = ok && (f == 1 << 1 || f == 1 << 3); --m; } if (ok) { debug { writefln("trivial each x: m = %s", m); } ans += Mint(2)^^m; } } // trivial each y { bool ok = true; long n = N; foreach (y, g; gs) { ok = ok && (g == 1 << 0 || g == 1 << 2); --n; } if (ok) { debug { writefln("trivial each y: n = %s", n); } ans += Mint(2)^^n; } } // 2 special bool[2] oks; if (G % 2 == 0) { foreach (s; 0 .. 2) { bool ok = true; foreach (k; 0 .. K) { ok = ok && (((X[k] + Y[k] + s) & 1) == (D[k] & 1)); } long m = M, n = N; foreach (x, f; fs) { ok = ok && !((f >> 1 & 1) && (f >> 3 & 1)); if ((f >> 1 & 1) || (f >> 3 & 1)) --m; } foreach (y, g; gs) { ok = ok && !((g >> 0 & 1) && (g >> 2 & 1)); if ((g >> 0 & 1) || (g >> 2 & 1)) --n; } if (ok) { debug { writefln("2 special: s = %s, m = %s, n = %s", s, m, n); } ans += Mint(2)^^(m + n); } oks[s] = ok; } } debug { writeln("oks = ", oks); } // other z foreach (i; 0 .. 2) { int d0, d1; final switch (i) { case 0: d0 = 0; d1 = 3; break; case 1: d0 = 1; d1 = 2; break; } bool ok = true; long g = G; foreach (z, p; ps) { ok = ok && (p == 1 << d0 || p == 1 << d1); --g; } if (ok) { Mint way = Mint(2)^^g; if (all == 0 || all == 1 << d0) way -= 1; if (all == 0 || all == 1 << d1) way -= 1; foreach (s; 0 .. 2) if (oks[s]) way -= 1; debug { writefln("other z: d0 = %s, d1 = %s, way = %s", d0, d1, way); } ans += way; } } // other w foreach (i; 0 .. 2) { int d0, d1; final switch (i) { case 0: d0 = 0; d1 = 1; break; case 1: d0 = 2; d1 = 3; break; } bool ok = true; long g = G; foreach (w, q; qs) { ok = ok && (q == 1 << d0 || q == 1 << d1); --g; } if (ok) { Mint way = Mint(2)^^g; if (all == 0 || all == 1 << d0) way -= 1; if (all == 0 || all == 1 << d1) way -= 1; foreach (s; 0 .. 2) if (oks[s]) way -= 1; debug { writefln("other w: d0 = %s, d1 = %s, way = %s", d0, d1, way); } ans += way; } } // TODO: 4 | G ga mada aru... writeln(ans); } } } catch (EOFException e) { } }