You have a collection of ~n~ pokemon which can have one of ~t~ different types. Type 1 beats type 2, type 2 beats type 3, ... , type ~t~ beats type 1. You are given ~q~ statements about the pokemon, stating that one pokemon beats another. You are tasked with deciding whether a statement contradicts the previous statements. If a statement does contradict the previous statements, you may assume it is false for all future statements.

Types beat only the next type along, and no other types, and pokemon can only have 1 type.

Input

First line contains integers ~n~, ~t~ and ~q~. The following ~q~ lines are of the following form: a b stating that pokemon a beats pokemon b.

Output

For each statement, output a line containing Yes or No, stating whether the statement creates a contradiction.

Constraints

• ~1 \le a,b \le n~
• ~1 \le n,t,q \le 5\times10^5~

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