有一个 2D 坐标平面,范围从 $$$(0,0)$$$ 到 $$$(x, y)$$$。您位于 $$$(0,0)$$$,并且想要前往 $$$(x, y)$$$。
然而,有$$$n$$$个水平激光,第$$$i$$$个激光连续跨越$$$(0, a_i)$$$到$$$(x, a_i)$$$。此外,还有$$$m$$$垂直激光器,第$$$i$$$个激光器连续跨越$$$(b_i, 0)$$$到$$$(b_i,y)$$$。
您可以向任意方向移动以到达 $$$(x, y)$$$,但您的移动必须是位于平面内的连续曲线。每次穿过垂直或水平激光时,都算作一次穿过。特别是,如果您经过两个激光之间的交点,则算作 两个路口.
例如,如果 $$$x = y = 2$$$、$$$n = m = 1$$$、$$$a = [1]$$$、$$$b = [1]$$$,则移动可以如下:
到达 $$$(x, y)$$$ 所需的最少交叉次数是多少?
输入
第一行包含 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含四个整数 $$$n$$$、$$$m$$$、$$$x$$$ 和 $$$y$$$ ($$$1 \leq n, m \leq 2 \cdot 10^5, 2 \leq x ,y \leq 10^9$$$)。
以下行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \lt a_i \lt y$$$) — 水平激光的 y 坐标。对于所有$$$i \gt 1$$$,保证$$$a_i \gt a_{i-1}$$$。
以下行包含 $$$m$$$ 整数 $$$b_1, b_2, \ldots, b_m$$$ ($$$0 \lt b_i \lt x$$$) — 垂直激光的 x 坐标。对于所有$$$i \gt 1$$$,保证$$$b_i \gt b_{i-1}$$$。
保证所有测试用例的 $$$n$$$ 和 $$$m$$$ 之和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出达到 $$$(x, y)$$$ 所需的最小交叉数。
示例
输入复制
21 1 2 2112 1 100000 10000042 5832
输出复制
2 3