#P9671. Permutation Subsegment Parity

    ID: 22818 Type: Default 1000ms 256MiB

Permutation Subsegment Parity

Permutation Subsegment Parity

Let the value of a sequence be the sum of all numbers in it. Given two positive integers \(n\) and \(k\), determine whether there exists a permutation of length \(n\) such that the values of all contiguous subsegments of length \(k\) share the same parity (i.e. they are either all odd or all even).

A permutation of length \(n\) is a sequence in which each integer from \(1\) to \(n\) appears exactly once. A subsegment is a contiguous part of the permutation.

If such a permutation exists, output YES on the first line and on the second line output one valid permutation (numbers separated by spaces). Otherwise, output NO.

Note: A subsegment of length \(k\) has a value equal to the sum of its \(k\) numbers. The condition requires that the parity (evenness or oddness) of this sum is the same for every subsegment of length \(k\).

Observation: If you denote the permutation as \(a_1,a_2,\dots,a_n\), note that the subsegment starting at index \(i\) (i.e. \(a_i + a_{i+1} + \dots + a_{i+k-1}\)) and the next subsegment starting at \(i+1\) differ by \(a_{i+k} - a_i\). Thus, for the parity to remain constant, it is necessary and sufficient that for every valid \(i\), \(a_{i}\) and \(a_{i+k}\) have the same parity. This essentially partitions the permutation indices into \(k\) groups according to their residue modulo \(k\); all numbers in the same group must have the same parity. This constraint, combined with the available numbers, leads to a partitioning problem which you must solve to construct a valid permutation if one exists.

inputFormat

The input consists of a single line containing two space-separated integers (n) and (k) (1 ≤ (n) ≤ 10^5, 1 ≤ (k) ≤ (n)).

outputFormat

If a valid permutation exists, output "YES" on the first line and a valid permutation ((n) space-separated integers) on the second line. Otherwise, output "NO".

sample

3 2
YES

1 2 3

</p>