您的位置:首页 > 健康 > 美食 > 湖南靠谱seo优化费用_设计公司起名及寓意_广州日新增51万人_最新新闻事件今天

湖南靠谱seo优化费用_设计公司起名及寓意_广州日新增51万人_最新新闻事件今天

2025/4/3 6:02:55 来源:https://blog.csdn.net/jj12345jj198999/article/details/146714972  浏览:    关键词:湖南靠谱seo优化费用_设计公司起名及寓意_广州日新增51万人_最新新闻事件今天
湖南靠谱seo优化费用_设计公司起名及寓意_广州日新增51万人_最新新闻事件今天

time limit per test

2 seconds

memory limit per test

256 megabytes

Given an array aa of nn integers, an array bb of mm integers, and an even number kk.

Your task is to determine whether it is possible to choose exactly k2k2 elements from both arrays in such a way that among the chosen elements, every integer from 11 to kk is included.

For example:

  • If a=[2,3,8,5,6,5]a=[2,3,8,5,6,5], b=[1,3,4,10,5]b=[1,3,4,10,5], k=6k=6, then it is possible to choose elements with values 2,3,62,3,6 from array aa and elements with values 1,4,51,4,5 from array bb. In this case, all numbers from 11 to k=6k=6 will be included among the chosen elements.
  • If a=[2,3,4,5,6,5]a=[2,3,4,5,6,5], b=[1,3,8,10,3]b=[1,3,8,10,3], k=6k=6, then it is not possible to choose elements in the required way.

Note that you are not required to find a way to choose the elements — your program should only check whether it is possible to choose the elements in the required way.

Input

The first line of the input contains a single integer tt (1≤t≤1041≤t≤104) — the number of test cases. The descriptions of the test cases follow.

The first line of each test case contains three integers nn, mm, and kk (1≤n,m≤2⋅1051≤n,m≤2⋅105, 2≤k≤2⋅min(n,m)2≤k≤2⋅min(n,m), kk is even) — the length of array aa, the length of array bb, and the number of elements to be chosen, respectively.

The second line of each test case contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤1061≤ai≤106) — the elements of array aa.

The third line of each test case contains mm integers b1,b2,…,bmb1,b2,…,bm (1≤bj≤1061≤bj≤106) — the elements of array bb.

It is guaranteed that the sum of values nn and mm over all test cases in a test does not exceed 4⋅1054⋅105.

Output

Output tt lines, each of which is the answer to the corresponding test case. As the answer, output "YES" if it is possible to choose k2k2 numbers from each array in such a way that among the chosen elements, every integer from 11 to kk is included. Otherwise, output "NO".

You can output each letter in any case (lowercase or uppercase). For example, the strings "yEs", "yes", "Yes", and "YES" will be accepted as a positive answer.

Example

Input

Copy

 

6

6 5 6

2 3 8 5 6 5

1 3 4 10 5

6 5 6

2 3 4 5 6 5

1 3 8 10 3

3 3 4

1 3 5

2 4 6

2 5 4

1 4

7 3 4 4 2

1 4 2

2

6 4 4 2

1 5 2

3

2 2 1 4 3

Output

Copy

YES
NO
YES
YES
NO
NO

Note

In the first test case of the example, it is possible to choose elements equal to 22, 33, and 66 from array aa and elements equal to 11, 44, and 55 from array bb. Thus, all numbers from 11 to k=6k=6 are included among the chosen elements.

In the second test case of the example, it can be shown that it is not possible to choose exactly three elements from each array in the required way.

In the third test case of the example, it is possible to choose elements equal to 11 and 33 from array aa and elements equal to 22 and 44 from array bb. Thus, all numbers from 11 to k=4k=4 are included among the chosen elements.

解题说明:此题是一道数学题,要从a[i]和b[i]中分别选k/2个元素,以便所选元素包含从 1 到 k 的每个整数。此题采用C++来做,可以对两个数组进行从小到大排序,把小于k的全部找出来放在集合里面,然后根据集合里面数据内容判断是否满足覆盖1-k的情况。

#include<bits/stdc++.h>
#include<iostream>
using namespace std;
#define ll long long intvoid solve() 
{ll n, m, k;cin >> n >> m >> k;vector<ll> a(n), b(m);for (int i = 0; i < n; i++){cin >> a[i];}for (int i = 0; i < m; i++){cin >> b[i];}sort(a.begin(), a.end());sort(b.begin(), b.end());set<ll> s1, s2;for (int i = 0; i < n; i++){if (a[i] <= k)s1.insert(a[i]);}for (int i = 0; i < m; i++) {if (b[i] <= k)s2.insert(b[i]);}set<ll> s;if (s1.size() < k / 2 || s2.size() < k / 2){cout << "NO" << endl;return;}for (auto i : s1){s.insert(i);}for (auto i : s2){s.insert(i);}for (int i = 1; i <= k; i++){if (s.find(i) == s.end()){cout << "NO" << endl;return;}}cout << "YES" << endl;
}int main() 
{ll t;cin >> t;while (t--){solve();}return 0;
}


 

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com