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
| #include <bits/stdc++.h>
using namespace std;
int mread() {
int ret=0,f=1;
char c=getchar();
while(c<'0' || c>'9') {
if(c=='-')f=-1;
c=getchar();
}
do {
ret=ret*10+c-'0';
c=getchar();
} while('0'<=c &&c<='9');
return ret*f;
}
#define MAXN 200100
int n,d;
int mmin[MAXN<<2],lazy[MAXN<<2],m_id[MAXN<<2];
struct rec {
bool typ;
int l,r;
} ;
vector<rec> lines[MAXN<<2];
int ql,qr,qval;
void push_down(int id) {
if(lazy[id]) {
mmin[id<<1]+=lazy[id];
mmin[id<<1|1]+=lazy[id];
lazy[id<<1]+=lazy[id];
lazy[id<<1|1]+=lazy[id];
lazy[id]=0;
}
}
void upd(int id) {
mmin[id]=min(mmin[id<<1],mmin[id<<1|1]);
m_id[id]=(mmin[id<<1] < mmin[id<<1|1]) ? m_id[id<<1] : m_id[id<<1|1];
}
void change(int id,int l,int r) {
if(ql<=l && r<=qr) {
mmin[id]+=qval;
lazy[id]+=qval;
return ;
}
push_down(id);
int mid=l+r>>1;
if(ql<=mid)change(id<<1,l,mid);
if(mid<qr)change(id<<1|1,mid+1,r);
upd(id);
}
void build(int id,int l,int r) {
if(l==r) {
m_id[id]=l;
return ;
}
int mid=(l+r)>>1;
build(id<<1,l,mid);
build(id<<1|1,mid+1,r);
upd(id);
}
const int INF = 0x3f3f3f3f;
int main() {
int l1,l2,r1,r2;
int x1,x2,y1,y2;
bool flag=true;
n=mread(),d=mread();
for(int i=1; i<=n; i++) {
x1=mread(),y1=mread(),x2=mread(),y2=mread();
if(x2-x1>=d && y2-y1>=d)
flag=false;
else {
l1=(x1%d+d)%d;
l2=(x2%d+d)%d;
r1=(y1%d+d)%d;
r2=(y2%d+d)%d;
if(x2-x1>=d)l1=0,l2=d;
if(y2-y1>=d)r1=0,r2=d;
if(l1 < l2) {
if(r1 > r2) {
lines[l1].push_back({true,0,r2-1});
lines[l1].push_back({true,r1,d-1});
lines[l2].push_back({false,0,r2-1});
lines[l2].push_back({false,r1,d-1});
} else {
lines[l1].push_back({true,r1,r2-1});
lines[l2].push_back({false,r1,r2-1});
}
} else {
if(r1 > r2) {
lines[0].push_back({true,0,r2-1});
lines[0].push_back({true,r1,d-1});
lines[l2].push_back({false,0,r2-1});
lines[l2].push_back({false,r1,d-1});
lines[l1].push_back({true,0,r2-1});
lines[l1].push_back({true,r1,d-1});
} else {
lines[0].push_back({true,r1,r2-1});
lines[l2].push_back({false,r1,r2-1});
lines[l1].push_back({true,r1,r2-1});
}
}
}
}
if(flag==false) {
printf("NO\n");
return 0;
}
flag=false;
build(1,0,d-1);
for(int i=0; i<d; i++) {
for(int j=0; j<lines[i].size(); j++) {
ql=lines[i][j].l,qr=lines[i][j].r;
if(ql<=qr) {
qval=((lines[i][j].typ==true) ? 1 : -1);
change(1,0,d-1);
}
}
if(mmin[1]==0) {
printf("YES\n");
printf("%d %d\n",i,m_id[1]);
return 0;
}
}
printf("NO\n");
return 0;
}
|