# Codeforces Round #624 (Div. 3) B - WeirdSort

B - WeirdSort

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given an array aa of length nn.

You are also given a set of distinct positions p1,p2,…,pmp1,p2,…,pm, where 1≤pi<n1≤pi<n. The position pipi means that you can swap elements a[pi]a[pi] and a[pi+1]a[pi+1]. You can apply this operation any number of times for each of the given positions.

Your task is to determine if it is possible to sort the initial array in non-decreasing order (a1≤a2≤⋯≤ana1≤a2≤⋯≤an) using only allowed swaps.

For example, if a=[3,2,1]a=[3,2,1] and p=[1,2]p=[1,2], then we can first swap elements aa and aa (because position 22 is contained in the given set pp). We get the array a=[3,1,2]a=[3,1,2]. Then we swap aa and aa (position 11 is also contained in pp). We get the array a=[1,3,2]a=[1,3,2]. Finally, we swap aa and aa again and get the array a=[1,2,3]a=[1,2,3], sorted in non-decreasing order.

You can see that if a=[4,1,2,3]a=[4,1,2,3] and p=[3,2]p=[3,2] then you cannot sort the array.

You have to answer tt independent test cases.

Input

The first line of the input contains one integer tt (1≤t≤1001≤t≤100) — the number of test cases.

Then tt test cases follow. The first line of each test case contains two integers nn and mm (1≤m<n≤1001≤m<n≤100) — the number of elements in aa and the number of elements in pp. The second line of the test case contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤1001≤ai≤100). The third line of the test case contains mm integers p1,p2,…,pmp1,p2,…,pm (1≤pi<n1≤pi<n, all pipi are distinct) — the set of positions described in the problem statement.

Output

For each test case, print the answer — "YES" (without quotes) if you can sort the initial array in non-decreasing order (a1≤a2≤⋯≤ana1≤a2≤⋯≤an) using only allowed swaps. Otherwise, print "NO".

Example

input

```6
3 2
3 2 1
1 2
4 2
4 1 2 3
3 2
5 1
1 2 3 4 5
1
4 2
2 1 4 3
1 3
4 2
4 3 2 1
1 3
5 2
2 1 2 3 3
1 4```

output

```YES
NO
YES
YES
NO
YES```

```#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rg register ll
#define inf 2147483647
#define lb(x) (x&(-x))
ll sz,n;
template <typename T> inline void read(T& x)
{
x=0;char ch=getchar();ll f=1;
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}x*=f;
}
inline ll query(ll x){ll res=0;while(x){res+=sz[x];x-=lb(x);}return res;}
struct node
{
ll val,pos;
}p;
inline bool cmp(const node&a,const node&b)
{
if(a.val==b.val)return a.pos<b.pos;
return a.val<b.val;
}
ll t,f,q;
inline void init(ll m)
{
memset(f,0,sizeof(f));
for(rg i=1;i<=100;i++)f[i]=i;
}
inline ll fa(ll x)
{
return f[x]==x?x:f[x]=fa(f[x]);
}
inline void merge(ll x,ll y)
{
ll fx=fa(x),fy=fa(y);
if(fx!=fy)
{
f[fy]=fx;
}
}
int main()
{
cin>>t;
for(rg i=1;i<=t;i++)
{
ll n,m,sum=0;
cin>>n>>m;
init(m);
for(rg i=1;i<=n;i++)cin>>p[i].val,p[i].pos=i;
for(rg j=1;j<=m;j++)cin>>q[j],merge(q[j],q[j]+1);
sort(p+1,p+1+n,cmp);
for(rg j=1;j<=n;j++)
{
if(fa(p[j].pos)==fa(j))
{
sum++;
}
}
sum==n?cout<<"YES"<<endl:cout<<"NO"<<endl;
}
while(1)getchar();
return 0;

}
/*
3 2 1
1 2
*/```

0 条评论

• ### Codeforces Round #633 (Div. 2) A Filling Diamonds （假题，观察）

You have integer nn. Calculate how many ways are there to fully cover belt-like ...

• ### Codeforces Round #424 (Div. 1, rated, based on VK Cup Finals) B. Cards Sorting 树状数组+技巧

Vasily has a deck of cards consisting of n cards. There is an integer on each of...

• ### PAT (Advanced Level) Practice 1146 Topological Order (25分)

This is a problem given in the Graduate Entrance Exam in 2018: Which of the foll...

• ### Access the OData service exposed by your CDS view via Smart Business Tile

It is possible to configure a Smart business tile which consumes the OData servi...

• ### 使用SAP S/4HANA Smart Business Tile消费CDS view OData服务

版权声明：本文为博主汪子熙原创文章，未经博主允许不得转载。 https://jerry.bl...

• ### 遇到SAP WebClient UI的白屏错误，应该如何分析？

I have already written one blog How to persist the ui exception so you can view ...

• ### 2014---多校训练一（A Couple doubi）

Couple doubi Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768...

• ### Codeforces Round #408 (Div. 2)(A.水,B,模拟)

A. Buying A House time limit per test:2 seconds memory limit per test:256 megaby...

• ### python 卷积函数_用Python计算两个函数的卷积

What is a convolution? OK, that’s not such a simple question. Instead, I am will...

• ### 如何修复破碎的手机或平板电脑屏幕（ mobile tech smartphone)

如何修复破碎的手机或平板电脑屏幕（ mobile tech  smartphone)

### 活动推荐 