该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

在深度学习中，各种张量操作层（如 reshape、transpose、flatten）在构造网络时常被使用。

给定初始张量为一维向量，其 shape 为 [m]。现在你获得了 n 个计算层，每个计算层描述为下列三种操作之一：

1. $reshape \ k \ a_1 \ a_2 \dots a_k$ 将当前张量重塑为 shape 为 (a₁, a₂, ..., aₖ) 的张量。要求：新 shape 的各维乘积必须等于$m$，否则操作非法。
2. $transpose \ k \ p_1 \ p_2 \dots p_k$ 将当前张量的各个维度按照给定顺序置换。其中 k 必须等于当前张量的维数，且 (p₁, p₂, ..., pₖ) 必须为 {1, 2, ..., k} 的一个排列。否则操作非法。
3. $flatten$ 将当前张量展平为一维向量，shape 为 [P]，其中 P 为当前张量所有维度的乘积。该操作始终合法。

这 n 个操作可以按照任意顺序排列。你的任务是判断是否存在一种排列顺序，使得从初始张量 [m] 出发，依次执行所有层时，每一步操作都是合法的（即没有非法操作发生）。

输入格式

• 第一行给出一个正整数 $T$($1 \le T \le 1000$)，表示测试样例的组数。
• 对于每组样例：
  • 第一行包含两个正整数：n 和 m ($1 \le n \le 30, 1 \le m \le 10^3$)，分别表示操作层数和初始向量长度。
  • 接下来有 n 行，每行描述一个计算层操作，格式为上述三种操作之一，其中，$1 \le k \le 4, 1 \le a_i \le 10$。

输出格式

对于每组样例，输出一行：

• 如果存在一种排列顺序使得所有操作依次合法，则输出 YES；
• 否则输出 NO。

样例

输入

2
3 24
reshape 3 2 3 4
transpose 3 3 1 2
flatten
3 24
reshape 2 3 10
transpose 1 1
flatten

输出

YES
NO

样例说明：

• 第一组样例中，初始向量为

  [24]
  

  。若按原顺序执行：

  • reshape 3 2 3 4：合法（2×3×4=24），当前 shape 变为 (2,3,4)；
  • transpose 3 3 1 2：合法，当前 shape 变为 (4,2,3)；
  • flatten：合法，当前 shape 变为 [24]。 因此存在一种排列（这里原顺序即为合法排列），答案为 YES。

• 第二组样例中，无论如何排列操作，都无法满足所有操作均合法，所以答案为 NO。