题目描述

爱丽丝和格林在玩游戏。游戏规则如下：

• 爱丽丝先手。
• 初始有一个集合 $S=\{1,2,\ldots,n\}$，以及一个空序列 $P$。
• 双方轮流从 $S$ 中选择一个数 $x$，将 $x$ 加入序列 $P$ 的末尾，并从 $S$ 中删除 $x$。

此外，还有一个给定的正整数 $k$ 用于判定胜负。本题有两套胜负规则：

• 规则 1：第一次使得 $P$ 的最长上升子序列长度变成 $k$ 的选手获胜；或者，当对手无法操作时（也就是 $S$ 被删空了）也获胜。
• 规则 2：第一次使得 $P$ 的最长上升子序列长度变成 $k$ 的选手失败；或者，当自己无法操作时（也就是 $S$ 被删空了）也失败。

现在，游戏已经进行了 $q$ 轮。保证 $q$ 为偶数，也就是说，爱丽丝和格林都已经分别操作了 $\frac q2$ 次。依次给出这 $q$ 次操作中他们选择的数

$$a_1,a_2,\ldots,a_q,$$

并保证此时还没有分出胜负。

由于 $q$ 是偶数，所以接下来仍然是爱丽丝先手。假设接下来的游戏过程中，爱丽丝和格林都绝顶聪明，你需要判断爱丽丝是否必胜。

若爱丽丝必胜，还需要求出爱丽丝接下来的第一步（也就是整个游戏的第 $q+1$ 步）有多少种操作方案能够使她最终获胜。

输入格式

本题有多组测试数据。

第一行包含一个正整数 $T$，表示测试数据组数。

接下来 $T$ 组测试数据，每组测试数据的格式如下：

• 第一行包含四个正整数 $n,v,q,k$。其中 $n,q,k$ 的含义如题目描述，$v\in\{1,2\}$ 表示使用第几套规则。
• 第二行包含 $q$ 个互不相同的正整数 $a_1,a_2,\ldots,a_q$，含义如题目描述。

输出格式

输出 $T$ 行。

对于每组测试数据，首先输出一个字符串 YES 或 NO，表示爱丽丝是否必胜。

若答案为 YES，则还需要在同一行输出一个正整数，表示爱丽丝第一步可行的操作方案数。两个输出项之间用一个空格分隔。

样例 1

输入

10
9 1 6 7
2 3 4 5 8 9
6 1 2 4
3 6
18 1 16 18
1 2 3 13 5 6 7 8 9 10 12 14 15 16 17 18
11 1 8 10
4 2 3 5 7 8 9 10
9 1 2 5
8 4
20 1 12 13
2 6 7 11 12 14 1 9 18 15 19 20
11 1 10 9
1 10 6 3 5 7 8 9 11 4
7 1 6 9
2 3 5 4 6 7
10 1 2 19
2 4
5 1 2 6
2 3

输出

YES 3
NO
NO
YES 3
YES 7
NO
YES 1
YES 1
NO
YES 3

数据范围

对于全部测试数据：

$$1\le T\le 1000,$$ $$3\le n\le 10^5, \qquad v\in\{1,2\}, \qquad 2\le k\le 10^5, \qquad 2\le q<n,$$

$q$ 为偶数，并且所有测试数据满足：

$$\sum n\le 10^6, \qquad \sum q\le 10^6, \qquad \sum k\le 10^6.$$

子任务

子任务编号	$n\le$	$v=$	特殊性质	分值
1	$5$	$1$	$k\le 25$	7
2		$2$
3	$100$	$1$	$a_i=i$	18
4	$10^5$		无	29
5	$100$	$2$	$a_i=i$	14
6	$10^5$		无	25