You have ~n~ pokemon. Each pokemon has exactly one type, an integer between ~1~ and ~t~ inclusive. Types form a cycle of matchups: type ~i~ beats type ~i + 1~ for ~1 \le i < t~, and type ~t~ beats type ~1~. A type beats only that next type in the cycle — not itself, and not any other type.

The types of the pokemon are unknown. You are given ~q~ statements in order, each claiming that one pokemon beats another. Process the statements one by one. For each statement, decide whether there exists an assignment of types to the pokemon that makes this statement true together with all previously accepted statements. If so, accept the statement and output Yes; otherwise reject it and output No. Rejected statements are discarded and are not used when checking later statements.

Input

The first line contains integers ~n~, ~t~, and ~q~.

The following ~q~ lines each contain two integers ~a~ and ~b~, stating that pokemon ~a~ beats pokemon ~b~.

Output

For each statement, output a line containing Yes or No, indicating whether the statement is accepted.

Constraints

• ~1 \le n, q \le 5 \times 10^5~
• ~2 \le t \le 5 \times 10^5~
• ~1 \le a, b \le n~

Example 1

Input

5 3 10
3 3
1 1
2 4
3 3
4 4
5 4
3 5
4 3
1 3
2 5

Output

No
No
Yes
No
No
Yes
Yes
Yes
Yes
No

Example 2

Input

8 4 20
4 3
4 4
4 3
4 3
5 5
3 6
6 3
4 4
8 7
1 2
8 2
3 6
6 8
4 5
2 8
3 6
7 6
5 8
8 2
1 6

Output

Yes
No
Yes
Yes
No
Yes
No
No
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
No
No
Yes
No