AIO Practice – Pairing Cards

You have found an unusual deck of N cards, where N is an even integer. Each card has an integer value written on it, and the ith card has value A_i.

Your task is to rearrange the N cards into N/2 pairs such that each card belongs to exactly one pair. However, you are only allowed to pair two cards with values A_i and A_j if at least one of the following holds:

• The absolute difference of their values equals D (|Ai − Aj| = D)
• The sum of their values equals S (Ai + Aj = S)

You are given integers D and S. Determine whether the cards can be divided into valid pairs.

Subtasks and Constraints

• 2 ≤ N ≤ 200000 and N is even
• 0 ≤ D, S ≤ 1000000
• 1 ≤ Ai ≤ 1000000
• Ai ≤ Ai+1 (values are sorted)

Input

• First line: N D S
• Second line: N integers A1 A2 ... AN

Your function should be named:

solve(N, D, S, A)

6 2 0
1 1 2 3 3 4

6 2 0
1 1 3 3 5 5

8 0 8
1 2 3 4 4 5 6 7

4 7 8
1 3 5 8

YES

NO

YES

YES