The answer is the number of $$$1$$$s modulo $$$2$$$.

We can get that by adding '-' before the $$$\text{2nd}, \text{4th}, \cdots, 2k\text{-th}$$$ $$$1$$$, and '+' before the $$$\text{3rd}, \text{5th}, \cdots, 2k+1\text{-th}$$$ $$$1$$$.

#include <bits/stdc++.h>
using namespace std;

char c[1005];
int main() {
  int t;
  scanf("%d", &t);
  int n;
  while (t--) {
    scanf("%d", &n);
    scanf("%s", c + 1);
    int u = 0;
    for (int i = 1; i <= n; ++i) {
      bool fl = (c[i] == '1') && u;
      u ^= (c[i] - '0');
      if (i != 1) putchar(fl ? '-' : '+');
    }
    putchar('\n');
  }
}

First, We can divide $$$n$$$ cells into $$$\left\lceil\frac{n}{k}\right\rceil$$$ segments that except the last segment, all segments have length $$$k$$$. Then in each segment, the colors in it are pairwise different. It's easy to find any $$$a_i$$$ should be smaller than or equal to $$$\left\lceil\frac{n}{k}\right\rceil$$$.

Then we can count the number of $$$a_i$$$ which is equal to $$$\left\lceil\frac{n}{k}\right\rceil$$$. This number must be smaller than or equal to $$$n \bmod k$$$, which is the length of the last segment.

All $$$a$$$ that satisfies the conditions above is valid. We can construct a coloring using the method below:

First, we pick out all colors $$$i$$$ that $$$a_i=\left\lceil\frac{n}{k}\right\rceil$$$, then we use color $$$i$$$ to color the $$$j$$$-th cell in each segment.

Then we pick out all colors $$$i$$$ that $$$a_i<\left\lceil\frac{n}{k}\right\rceil-1$$$ and use these colors to color the rest of cells with cyclic order(i.e. color $$$j$$$-th cell of the first segment, of second the segment ... of the $$$\left\lceil\frac{n}{k}\right\rceil$$$ segment, and let $$$j++$$$. when one color is used up, we begin to use the next color)

At last, we pick out all colors $$$i$$$ that $$$a_i=\left\lceil\frac{n}{k}\right\rceil-1$$$, and color them with the cyclic order.

This method will always give a valid construction.

#include <bits/stdc++.h>
using namespace std;

int main() {
  int t;
  scanf("%d", &t);
  while (t--) {
    int n, m, k;
    scanf("%d %d %d", &n, &m, &k);
    int fl = 0;
    for (int i = 1; i <= m; ++i) {
      int a;
      scanf("%d", &a);
      if (a == (n + k - 1) / k) ++fl;
      if (a > (n + k - 1) / k) fl = 1 << 30;
    }
    puts(fl <= (n - 1) % k + 1 ? "YES" : "NO");
  }
}