题目描述

在从 $(0,0)$ 到 $(x,y)$ 的矩形平面内，有 $n$ 条水平激光和 $m$ 条竖直激光。每穿过一条激光计一次；若经过交点，则同时计两次。求从左下角到右上角连续移动所需的最少穿越次数。

输入格式

第一行包含整数 $t$。每组数据先给出 $n,m,x,y$，再给出 $n$ 个水平激光的纵坐标，最后给出 $m$ 个竖直激光的横坐标。坐标均严格递增。

输出格式

对每组数据输出最少穿越次数。

2
1 1 2 2
1
1
2 1 100000 100000
42 58
32

2
3

数据范围与提示

$1 \le t \le 10^4$。

每组测试数据中，$1 \le n,m \le 2 \cdot 10^5$，$2 \le x,y \le 10^9$。

水平激光坐标满足 $0 < a_i < y$，且 $a_i$ 严格递增。

竖直激光坐标满足 $0 < b_i < x$，且 $b_i$ 严格递增。

保证所有测试数据中 $n+m$ 的总和不超过 $2 \cdot 10^5$。

来源

本题来自 Codeforces Round 1050 (Div. 4)，原题编号 CF2148B，英文题名 Lasers。