鲍里斯认为国际象棋是一项乏味的游戏。所以他提前离开了比赛,去了一家理发店,因为他的头发有点乱。
他当前的头发可以用数组 $$$a_1,a_2,\ldots, a_n$$$ 来描述,其中 $$$a_i$$$ 是位置 $$$i$$$ 处头发的高度。他想要的发型可以用数组 $$$b_1,b_2,\ldots, b_n$$$ 以类似的方式描述。
理发师有 $$$m$$$ 剃须刀。每个都有自己的大小,最多可以使用一次。在一次手术中,他选择了一把剃刀,剪掉了鲍里斯的一段头发。更正式地说,操作是:
- 选择任何以前没有使用过的剃须刀,让它的大小为$$$x$$$;
- 选择一个段 $$$[l,r]$$$ ($$$1\leq l \leq r \leq n$$$);
- 设置 $$$a_i := \min (a_i,x)$$$ 为每个 $$$l\leq i \leq r$$$;
请注意,某些剃须刀可能具有相同的尺寸 - 理发师只能选择与尺寸为 $$$x$$$ 的剃须刀数量相同的 $$$x$$$ 尺寸。
他可以执行任意数量的操作,只要任何剃刀最多使用一次,并且最后每个 $$$1 \leq i \leq n$$$ $$$a_i = b_i$$$ 即可。他不必使用所有剃须刀。
你能确定理发师能否给鲍里斯剪出他想要的发型吗?
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \leq t \leq 20\,000$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个正整数 $$$n$$$ ($$$3\leq n\leq 2\cdot 10^5$$$) — 数组 $$$a$$$ 和 $$$b$$$ 的长度。
每个测试用例的第二行包含 $$$n$$$ 正整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — 鲍里斯当前的头发。
每个测试用例的第三行包含 $$$n$$$ 正整数 $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \leq b_i \leq 10^9$$$) — Boris 想要的头发。
每个测试用例的第四行包含一个正整数 $$$m$$$ ($$$1 \leq m \leq 2\cdot 10^5$$$) — 剃须刀的数量。
每个测试用例的第五行包含 $$$m$$$ 正整数 $$$x_1,x_2, \ldots, x_m$$$ ($$$1 \leq x_i \leq 10^9$$$) — 剃须刀的尺寸。
保证所有测试用例的 $$$n$$$ 之和与 $$$m$$$ 之和不超过 $$$2\cdot 10^5$$$。
输出
对于每个测试用例,如果理发师可以根据需要修剪鲍里斯的头发,请打印“YES”。否则,打印“NO”。
您可以在任何情况下输出答案(大写或小写)。例如,字符串“yEs”、“yes”、“Yes”和“YES”将被识别为肯定响应。
示例
输入 #1
7 3 3 3 3 2 1 2 2 1 2 6 3 4 4 6 3 4 3 1 2 3 2 3 3 3 2 3 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 10 1 2 3 4 5 6 7 8 9 10 3 1 1 1 1 1 2 12 4 2 4 3 1 5 6 3 5 6 2 1 13 7 9 4 5 3 3 3 6 8 10 3 2 5 5 3 1 5 3 2 2 5 8 5 1 1 5 8 1 5 3 5 4 2 3 1 13 7 9 4 5 3 3 3 6 8 10 3 2 5 5 3 1 5 3 2 2 5 8 5 1 1 5 7 1 5 3 4 2 3 1 3 19747843 2736467 938578397 2039844 2039844 2039844 1 2039844
输出 #1
YES NO YES NO YES NO YES
注意
在第一个测试用例中,鲍里斯的头发最初是$$$[3,3,3]$$$。让我们描述理发师可以执行的一系列 $$$2$$$ 操作:
- 理发师在$$$[2,2]$$$段上使用尺寸为$$$1$$$的剃须刀;因此鲍里斯的头发变成$$$[3,1,3]$$$。
- 理发师在$$$[1,3]$$$段上使用尺寸为$$$2$$$的剃须刀;因此鲍里斯的头发变成$$$[2,1,2]$$$,这是所需的发型。
在第三个测试用例中,无需执行任何操作,因为鲍里斯的头发已经达到预期效果。
在第四个测试用例中,任何削减都无法以数组变为 $$$[1,1,2]$$$ 的方式增加 $$$[1,1,1]$$$ 中的第三个元素。