Nezzar has a binary string ss of length nn that he wants to share with his best friend, Nanako. Nanako will spend qq days inspecting the binary string. At the same time, Nezzar wants to change the string ss into string ff during these qq days, because it looks better.
It is known that Nanako loves consistency so much. On the ii-th day, Nanako will inspect a segment of string ss from position lil_i to position rir_i inclusive. If the segment contains both characters ‘0’ and ‘1’, Nanako becomes unhappy and throws away the string.
After this inspection, at the ii-th night, Nezzar can secretly change strictly less than half of the characters in the segment from lil_i to rir_i inclusive, otherwise the change will be too obvious.
Now Nezzar wonders, if it is possible to avoid Nanako being unhappy and at the same time have the string become equal to the string ff at the end of these qq days and nights.

Input

The first line contains a single integer tt (1≤t≤2⋅1051≤t≤2⋅10^5) — the number of test cases.
The first line of each test case contains two integers nn ,qq (1≤n≤2⋅105, 0≤q≤2⋅105).
The second line of each test case contains a binary string ss of length nn.
The third line of each test case contains a binary string ff of length nn.
Then qq lines follow, ii-th of them contains two integers lil_i, rir_i (1≤li≤ri≤n1≤l_i≤r_i≤n) — bounds of the segment, that Nanako will inspect on the ii-th day.
It is guaranteed that the sum of nn for all test cases doesn’t exceed 2⋅1052⋅10^5, and the sum of qq for all test cases doesn’t exceed 2⋅1052⋅10^5.

Output

For each test case, print “YES” on the single line if it is possible to avoid Nanako being unhappy and have the string ff at the end of qq days and nights. Otherwise, print “NO”.
You can print each letter in any case (upper or lower).

Example

input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
4
5 2
00000
00111
1 5
1 3
2 1
00
01
1 2
10 6
1111111111
0110001110
1 10
5 9
7 10
1 7
3 5
6 10
5 2
10000
11000
2 5
1 3

output

1
2
3
4
YES
NO
YES
NO

Note

In the first test case, 00000‾→000‾11→00111\underline{00000} \rightarrow \underline{000}11 \rightarrow 00111 is one of the possible sequences of string changes.
In the second test case, it can be shown that it is impossible to have the string ff at the end.

Translation

给出两个二进制字符串 ss 和 ff，有 qq 次操作，目标是将 ss 变为 ff。每次操作给一个区间 [li,ri][l_i,r_i]，若此时 sli∼sris_{l_i}\sim s_{r_i} 中 00 和 11 都存在，就定义为失败；否则可以修改严格小于区间一半长度数量的字符，最后若能达到目标就成功。

Idea

正向考虑非常麻烦，因为要顾及在后面的操作中不能让一段区间中出现既有 00 又有 11 的情况；不妨反向思考，一次反向考虑 qq 次操作，从 [lq,rq][l_q,r_q] 到 [l1,r1][l_1,r_1]，将 ff 变为 ss。
我们首先考虑 ff 一定能变为 ss，那么第 qq 次操作后，ss 就最终变成了 ff。考察 ff 中 [lq,rq][l_q,r_q] 这段区间，我们必须要保证在这次操作前 [lq,rq][l_q,r_q] 这段区间全 00 或全 11，然后将这段区间修改为 flq∼frqf_{l_q}\sim f_{r_q}。逆向操作，如果区间内有严格多数的 00 或 11，将区间内数字都变为多数，最后比较最后得到的字符串是否为 ss，这种方法带有反证法的思想。
用到的数据结构是区间修改、单点查询的线段树；叶节点是该位置上的数字（00 或 11），结点维护区间和，即区间内 11 的个数。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: CF1477B
Date: 2021 Jan. 31st
Description: Segment Tree, greedy
*******************************************************************/
#include<iostream>
#define lson rt<<1
#define	rson rt<<1|1
using namespace std;
const int N=200006;
int _;
int n,q;
char s[N],f[N];
int l[N],r[N];
struct segment{
	int l,r;//结点区间
	int num;//区间内1的个数
	int lazy;//结点懒惰标记
}tree[N<<2];
inline const int length(const int&);
inline void pushup(int);
inline void pushdown(int);
void build(int,int,int);
void update(int,int,int,int);
int query(int,int,int);
int main(){
	for(cin>>_;_;_--){
		cin>>n>>q;
		cin>>(s+1)>>(f+1);
		for(int i=1;i<=q;i++){
			cin>>l[i]>>r[i];
		}
		build(1,1,n);
		bool ok=1;
		for(int i=q;i>=1;i--){
			const int c1=query(1,l[i],r[i]);//区间内1的个数
			const int c0=r[i]-l[i]+1-c1;//区间内0的个数
			if(c0>c1){
				//区间内都变成0
				update(1,l[i],r[i],0);
			}else if(c0<c1){
				//区间内都变成1
				update(1,l[i],r[i],1);
			}else{
				ok=0;
				goto cont;
			}
		}
		for(int i=1;i<=n;i++){
			if(query(1,i,i)!=s[i]-'0'){
				ok=0;
				goto cont;
			}
		}
		cont:puts(ok?"YES":"NO");
	}
	return 0;
}
inline const int length(const int& id){
	return tree[id].r-tree[id].l+1;
}
inline void pushup(int rt){
	tree[rt].num=tree[lson].num+tree[rson].num;
}
inline void pushdown(int rt){
	if(~tree[rt].lazy){
		//用lazy更新子节点
		tree[lson].num=length(lson)*tree[rt].lazy;
		tree[rson].num=length(rson)*tree[rt].lazy;
		//下放标记
		tree[lson].lazy=tree[rson].lazy=tree[rt].lazy;
		//父亲结点lazy标记删除
		tree[rt].lazy=-1;
	}
}
void build(int rt,int l,int r){
	tree[rt]={l,r,0,-1};
	if(l==r){
		//num统计区间中1的个数
		tree[rt].num=f[l]-'0';
		return;//!!!!!!!
	}
	int mid=l+r>>1;
	build(lson,l,mid);
	build(rson,mid+1,r);
	pushup(rt);
}
void update(int rt,int l,int r,int v){
	if(l<=tree[rt].l&&tree[rt].r<=r){
		//找到一部分需要更新的区间
		//更新该结点，打上标记，不再向下更新
		tree[rt].num=v*length(rt);
		tree[rt].lazy=v;
		return;//!!!!!!!!!
	}
/*
	寻找其他区间
	将lazy标记下放
	继续搜索可以更新的区间
*/
//因为之后要pushup，这里必须要pushdown
	pushdown(rt);
	int mid=tree[rt].l+tree[rt].r>>1;
	//按区间交的关系更新子树
	if(l<=mid){
		update(lson,l,r,v);
	}
	if(r>mid){
		update(rson,l,r,v);
	}
	pushup(rt);//向上更新
}
int query(int rt,int l,int r){
	if(l<=tree[rt].l&&tree[rt].r<=r){
		//整一段区间有效
		return tree[rt].num;
	}
/*
	lazy标记下放
	继续搜索有效的区间
*/
	pushdown(rt);
	int mid=tree[rt].l+tree[rt].r>>1;
	int res=0;
	if(l<=mid){
		res+=query(lson,l,r);
	}
	if(r>mid){
		res+=query(rson,l,r);
	}
	return res;
}