import java.io.IOException; import java.io.InputStream; import java.io.OutputStream; import java.io.PrintStream; import java.io.PrintWriter; import java.lang.reflect.Array; import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Arrays; import java.util.Collection; import java.util.Collections; import java.util.Comparator; import java.util.List; import java.util.NoSuchElementException; import java.util.Objects; import java.util.PrimitiveIterator.OfInt; import java.util.PrimitiveIterator; import java.util.Queue; import java.util.Random; import java.util.function.IntBinaryOperator; import java.util.function.IntFunction; import java.util.function.IntToDoubleFunction; import java.util.function.IntToLongFunction; import java.util.function.IntUnaryOperator; import java.util.function.LongBinaryOperator; import java.util.function.Predicate; import java.util.function.ToIntFunction; import java.util.random.RandomGenerator; import java.util.stream.IntStream; import java.util.stream.Stream; public class Main { static MyPrintWriter pw = MyPrintWriter.getInstance(); static FastScanner sc = FastScanner.getInstance(); public static void main(String[] args) throws IOException { Thread.setDefaultUncaughtExceptionHandler((t, e) -> System.exit(1)); new Main().run(); pw.flush(); } void run() { int T = sc.nextInt(); for (int TEST = 0; TEST < T; TEST++) { int N = sc.nextInt(); int[] X = new int[2 * N]; int[] Y = new int[2 * N]; boolean[] F = new boolean[2 * N]; for (int i = 0; i < (2 * N); i++) { X[i] = sc.nextInt(); Y[i] = sc.nextInt(); F[i] = sc.next().charAt(0) == 'x'; } IntTreapMultiSet set0 = new IntTreapMultiSet(); IntTreapMultiSet set1 = new IntTreapMultiSet(); for (int i = 0; i < (2 * N); i++) { if (F[i]) { set0.add(Y[i]); } else { set1.add(X[i]); } } int c0 = 0; int c1 = 0; IntArrayList list0 = new IntArrayList(); IntArrayList list1 = new IntArrayList(); for (var es : set0.entryList()) { list0.add(((int) (es.value))); } for (var es : set1.entryList()) { list1.add(((int) (es.value))); } for (int i = 0; i < list0.size(); i++) { if ((list0.get(i) % 2) == 1) { list0.set(i, list0.get(i) - 1); c0++; } } for (int i = 0; i < list1.size(); i++) { if ((list1.get(i) % 2) == 1) { list1.set(i, list1.get(i) - 1); c1++; } } int m = Math.min(c0, c1); c0 -= m; c1 -= m; if (c0 > 0) { pw.printlnYesNo(ArrayUtils.sum(list1.toArray()) >= c0); } else if (c1 > 0) { pw.printlnYesNo(ArrayUtils.sum(list0.toArray()) >= c1); } else { pw.println("Yes"); } } } } class ArrayUtils { public static long sum(int[] a) { long ret = 0; for (int val : a) { ret += val; } return ret; } } class FastScanner { private static FastScanner instance = null; private final InputStream in = System.in; private final byte[] buffer = new byte[1 << 16]; private int ptr = 0; private int buflen = 0; private FastScanner() { } public static FastScanner getInstance() { if (instance == null) { instance = new FastScanner(); } return instance; } private boolean hasNextByte() { if (ptr < buflen) { return true; } ptr = 0; try { buflen = in.read(buffer); } catch (IOException e) { e.printStackTrace(); } return buflen > 0; } private int readByte() { if (hasNextByte()) { return buffer[ptr++]; } else { return -1; } } private boolean isPrintableChar(int c) { return (33 <= c) && (c <= 126); } public boolean hasNext() { while (hasNextByte() && (!isPrintableChar(buffer[ptr]))) { ptr++; } return hasNextByte(); } public String next() { if (!hasNext()) { throw new NoSuchElementException(); } StringBuilder sb = new StringBuilder(); int b = readByte(); while (isPrintableChar(b)) { sb.appendCodePoint(b); b = readByte(); } return sb.toString(); } public long nextLong() { if (!hasNext()) { throw new NoSuchElementException(); } long n = 0; boolean minus = false; int b = readByte(); if (b == '-') { minus = true; b = readByte(); } while ((b >= '0') && (b <= '9')) { // n = n * 10 + (b - '0'); n = ((n << 1) + (n << 3)) + (b - '0'); b = readByte(); } return minus ? -n : n; } public int nextInt() { return ((int) (nextLong())); } } /** * * * tailがa.lengthに比べて小さくなっても配列を取り直さない。 * * @param */ class IntArrayList implements Iterable { @SuppressWarnings("unchecked") int defaultCapacity = 16; int[] a; public int tail = 0; public IntArrayList() { a = new int[defaultCapacity]; } public void add(int v) { if (tail == a.length) { resize(2 * a.length); } a[tail] = v; tail++; } public int get(int id) { if ((id < 0) || (id >= tail)) { throw new IndexOutOfBoundsException(((((("get(" + id) + ")は添え字") + 0) + "以上") + (tail - 1)) + "以下に違反"); } return a[id]; } public void set(int id, int value) { if ((id < 0) || (id >= tail)) { throw new IndexOutOfBoundsException(); } a[id] = value; } void resize(int size) { a = Arrays.copyOf(a, size); } public int size() { return tail; } public int[] toArray() { return Arrays.copyOf(a, tail); } @Override public PrimitiveIterator.OfInt iterator() { return new PrimitiveIterator.OfInt() { int idx = 0; @Override public boolean hasNext() { return idx < tail; } @Override public int nextInt() { if (!hasNext()) { throw new NoSuchElementException(); } return get(idx++); } }; } @Override public boolean equals(Object o) { if (this == o) { return true; } if (!(o instanceof IntArrayList that)) { return false; } if (tail != that.tail) { return false; } for (int i = 0; i < tail; i++) { if (a[i] != that.a[i]) { return false; } } return true; } @Override public int hashCode() { int result = 1; for (int i = 0; i < tail; i++) { result = (31 * result) + a[i]; } return result; } @Override public String toString() { return Arrays.toString(toArray()); } } /** * {@code int} に特殊化した Treap ベースのマルチセット。 * 内部で {@link TreapMap} を使用しています。 */ class IntTreapMultiSet { private final TreapMap map; /** * 重複を含めた総要素数 */ private long size = 0; public IntTreapMultiSet() { map = new TreapMap(); } /** * 要素を {@code repeat} 回追加します。 * {@code repeat} が負の場合は削除を意味しますが、操作後の個数が負になる場合は {@link AssertionError} を投げます。 * * @param element * 追加する要素 * @param repeat * 追加する回数 * @complexity O(log N) (N は異なる要素の数) */ public void add(int element, long repeat) { if (repeat == 0) { return; } size += repeat; long num = map.getOrDefault(element, 0L) + repeat; if (num < 0) { throw new AssertionError(); } if (num == 0) { map.remove(element); } else { map.put(element, num); } } /** * 要素を1つ追加します。 * * @param element * 追加する要素 * @complexity O(log N) */ public void add(int element) { add(element, 1); } public static class Entry { public final int key; public final long value; public Entry(int key, long value) { this.key = key; this.value = value; } } /** * キーが要素、値が要素の個数であるエントリーのリストを返します。 * * @return エントリーのリスト * @complexity O(N) */ public List entryList() { List res = new ArrayList<>(); for (var e : map.entryList()) { res.add(new Entry(((int) (e.key)), e.value)); } return res; } /** * 異なる要素の数を返します。 * * @return 異なる要素の数 * @complexity O(1) */ public int numberDistinctElements() { return map.size(); } /** * 集合が空であるかどうかを返します。 * * @return 空であれば {@code true} * @complexity O(1) */ public boolean isEmpty() { return map.isEmpty(); } /** * 集合の状態を文字列として表します。 *
    *
  • 事前条件: 特になし。
  • *
  • 事後条件: 特になし。
  • *
  • 計算量: $O(N)$
  • *
  • 破壊的変更: なし。
  • *
* * @return 集合の状態を表す文字列 */ // 未テスト @Override public String toString() { if (isEmpty()) { return "空集合"; } else { StringBuilder sb = new StringBuilder(); boolean first = true; for (var entry : entryList()) { if (!first) { sb.append("\n"); } sb.append(entry.key).append(" が ").append(entry.value).append("個"); first = false; } return sb.toString(); } } /** * このマルチセットと別のオブジェクトの同値性を判定します。 * 内部の各要素とその個数が一致する場合に同値とみなします。 * *

計算量: $O(N)$($N$ は異なる要素の数)

* * @param obj * 比較対象のオブジェクト * @return 同値であれば true, そうでなければ false */ // 未テスト @Override public boolean equals(Object obj) { if (this == obj) { return true; } if (!(obj instanceof IntTreapMultiSet)) { return false; } IntTreapMultiSet other = ((IntTreapMultiSet) (obj)); if (this.size != other.size) { return false; } if (this.numberDistinctElements() != other.numberDistinctElements()) { return false; } List thisEntries = this.entryList(); List otherEntries = other.entryList(); if (thisEntries.size() != otherEntries.size()) { return false; } for (int i = 0; i < thisEntries.size(); i++) { Entry e1 = thisEntries.get(i); Entry e2 = otherEntries.get(i); if ((e1.key != e2.key) || (e1.value != e2.value)) { return false; } } return true; } /** * このマルチセットのハッシュコードを計算します。 * *

計算量: $O(N)$($N$ は異なる要素の数)

* * @return ハッシュコード */ // 未テスト @Override public int hashCode() { int result = 1; result = (31 * result) + Long.hashCode(size); for (Entry e : entryList()) { result = (31 * result) + Integer.hashCode(e.key); result = (31 * result) + Long.hashCode(e.value); } return result; } } class MyPrintWriter extends PrintWriter { private static MyPrintWriter instance = null; private MyPrintWriter() { super(System.out); } public static MyPrintWriter getInstance() { if (instance == null) { instance = new MyPrintWriter(); } return instance; } public void printlnYesNo(boolean flag) { println(flag ? "Yes" : "No"); } } /** *
    *
  • キーに関して二分探索木の順序を満たす
  • *
  • 優先度(priority)に関して最大ヒープの性質を満たす
  • *
*/ class TreapMap { static final Random rnd = new Random(); private int size = 0; public TreapMap() { } static class Node { long key; int priority; Node left; Node right; int size; long sum; long val; public Node(long key, long val) { this.key = key; this.val = val; this.priority = rnd.nextInt(); recalc(this); } } private Node root; public static void recalc(Node t) { if (t == null) { return; } t.sum = t.val; t.size = 1; if (t.left != null) { t.sum += t.left.sum; t.size += t.left.size; } if (t.right != null) { t.sum += t.right.sum; t.size += t.right.size; } } /** * 右回転(Right Rotation)を行います。 * *

次のように部分木を右回転させます: * *

     * y                x
     * / \     =>       / \
     * x   C            A   y
     * / \                  / \
     * A   B                B   C
     * 
* * @param y * 回転対象となる部分木の根 * @return 回転後の新しい部分木の根 */ private Node rotateRight(Node y) { Node x = y.left; y.left = x.right; x.right = y; recalc(y); recalc(x); return x; } /** * 左回転(Left Rotation)を行います。 * *

次のように部分木を左回転させます: * *

     * x                   y
     * / \       =>        / \
     * A   y               x   C
     * / \             / \
     * B   C           A   B
     * 
* * @param x * 回転対象となる部分木の根 * @return 回転後の新しい部分木の根 */ private Node rotateLeft(Node x) { Node y = x.right; x.right = y.left; y.left = x; recalc(x); recalc(y); return y; } private Node put(Node node, long key, long val) { if (node == null) { ++size; return new Node(key, val); } if (key < node.key) { node.left = put(node.left, key, val); if (node.left.priority > node.priority) { node = rotateRight(node); } } else if (key > node.key) { node.right = put(node.right, key, val); if (node.right.priority > node.priority) { node = rotateLeft(node); } } else { node.val = val; } recalc(node); return node; } public void put(long key, long val) { root = put(root, key, val); } public long getOrDefault(long key, long defaultValue) { return getOrDefaultValue(getRoot(), key, defaultValue); } private long getOrDefaultValue(Node node, long key, long defaultValue) { if (node == null) { return defaultValue; } if (key == node.key) { return node.val; } return key < node.key ? getOrDefaultValue(node.left, key, defaultValue) : getOrDefaultValue(node.right, key, defaultValue); } /** * Treap から指定したキーを削除。 * *

* 削除は次の手順で行われます: *

    *
  1. 二分探索木として削除対象ノードを見つける
  2. *
  3. 優先度に応じて回転し、削除対象ノードを葉へ押し下げる
  4. *
  5. 葉になったら削除する
  6. *
* * @param node * 部分木の根 * @param key * 削除するキー * @return 更新後の部分木の根 https://judge.yosupo.jp/submission/336359 */ private Node remove(Node node, long key) { if (node == null) { return null; } if (key < node.key) { node.left = remove(node.left, key); } else if (key > node.key) { node.right = remove(node.right, key); } else if ((node.left == null) && (node.right == null)) { --size; return null; } else if (node.left == null) { node = rotateLeft(node); node.left = remove(node.left, key); } else if (node.right == null) { node = rotateRight(node); node.right = remove(node.right, key); } else if (node.left.priority > node.right.priority) { node = rotateRight(node); node.right = remove(node.right, key); } else { node = rotateLeft(node); node.left = remove(node.left, key); } recalc(node); return node; } public void remove(long key) { root = remove(getRoot(), key); } public int size() { return size; } public boolean isEmpty() { return size == 0; } public static class Entry { public final long key; public final long value; public Entry(long key, long value) { this.key = key; this.value = value; } } /** * https://atcoder.jp/contests/abc406/submissions/73198102 * * @return */ public List entryList() { List res = new ArrayList<>(); inOrderEntries(getRoot(), res); return res; } private void inOrderEntries(Node node, List res) { if (node == null) { return; } inOrderEntries(node.left, res); res.add(new Entry(node.key, node.val)); inOrderEntries(node.right, res); } public Node getRoot() { return root; } /** * このマップと指定されたオブジェクトが等価であるか検証します。 * * @param o * 比較対象のオブジェクト * @return 等価であれば true, そうでなければ false $O(N)$ // 未テスト */ @Override public boolean equals(Object o) { if (this == o) { return true; } if (!(o instanceof TreapMap)) { return false; } TreapMap other = ((TreapMap) (o)); if (this.size() != other.size()) { return false; } List thisEntries = this.entryList(); List otherEntries = other.entryList(); for (int i = 0; i < thisEntries.size(); i++) { Entry e1 = thisEntries.get(i); Entry e2 = otherEntries.get(i); if ((e1.key != e2.key) || (e1.value != e2.value)) { return false; } } return true; } /** * このマップのハッシュコード値を返します。 * * @return ハッシュコード値 $O(N)$ // 未テスト */ @Override public int hashCode() { int h = 0; List entries = this.entryList(); for (Entry entry : entries) { h += Long.hashCode(entry.key) ^ Long.hashCode(entry.value); } return h; } } // --- Original Code --- // // // import java.io.IOException; // import java.util.Arrays; // // import library.tools.FastScanner; // import library.tools.MergeFiles; // import library.tools.MyPrintWriter; // import library.util.ArrayUtils; // import library.util.collections.IntArrayList; // import library.util.collections.IntTreapMultiSet; // // public class Main { // static MyPrintWriter pw = MyPrintWriter.getInstance(); // static FastScanner sc = FastScanner.getInstance(); // // public static void main(String[] args) throws IOException { // new Main().run(); // pw.flush(); // MergeFiles.export(); // } // // // void run() { // int T=sc.nextInt(); // for (int TEST = 0; TEST < T; TEST++) { // int N=sc.nextInt(); // int[]X=new int[2*N]; // int[]Y=new int[2*N]; // boolean[]F=new boolean[2*N]; // for (int i = 0; i < 2*N; i++) { // X[i]=sc.nextInt(); // Y[i]=sc.nextInt(); // F[i]=sc.next().charAt(0)=='x'; // } // IntTreapMultiSet set0=new IntTreapMultiSet(); // IntTreapMultiSet set1=new IntTreapMultiSet(); // for (int i = 0; i < 2*N; i++) { // if(F[i]) { // set0.add(Y[i]); // } else { // set1.add(X[i]); // } // } // int c0=0; // int c1=0; // IntArrayList list0=new IntArrayList(); // IntArrayList list1=new IntArrayList(); // for (var es : set0.entryList()) { // list0.add((int)es.value); // } // for (var es : set1.entryList()) { // list1.add((int)es.value); // } // for (int i = 0; i < list0.size(); i++) { // if(list0.get(i)%2==1) { // list0.set(i, list0.get(i)-1); // c0++; // } // } // for (int i = 0; i < list1.size(); i++) { // if(list1.get(i)%2==1) { // list1.set(i, list1.get(i)-1); // c1++; // } // } // int m=Math.min(c0, c1); // c0-=m; // c1-=m; // if (c0 > 0) { // pw.printlnYesNo(ArrayUtils.sum(list1.toArray()) >= c0); // } else if (c1 > 0) { // pw.printlnYesNo(ArrayUtils.sum(list0.toArray()) >= c1); // } else { // pw.println("Yes"); // } // } // } // // void tr(Object... objects) { // System.out.println(Arrays.deepToString(objects)); // } // } //