For problem statement at 2000-2999/2100-2199/2100-2109/2109/problemD.txt this is a correct solution, but verifier at 2000-2999/2100-2199/2100-2109/2109/verifierD.go ends with Mismatch on test 9: expected "111111111110", got "100011110010"
Input used:
12 18 1
2
1 2
1 3
1 4
4 5
4 6
4 7
2 8
1 9
7 10
7 11
7 12
1 10
4 10
2 6
2 11
5 8
5 11
2 7
exit status 1 can you fix the verifier? ```go
package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	var t int
	fmt.Fscan(in, &t)
	for ; t > 0; t-- {
		var n, m, l int
		fmt.Fscan(in, &n, &m, &l)
		A := make([]int, l)
		sumA := 0
		cntOdd := 0
		minOdd := int(1e9)
		for i := 0; i < l; i++ {
			fmt.Fscan(in, &A[i])
			sumA += A[i]
			if A[i]%2 == 1 {
				cntOdd++
				if A[i] < minOdd {
					minOdd = A[i]
				}
			}
		}

		adj := make([][]int, n)
		for i := 0; i < m; i++ {
			var u, v int
			fmt.Fscan(in, &u, &v)
			u--
			v--
			adj[u] = append(adj[u], v)
			adj[v] = append(adj[v], u)
		}

		dist := make([]int, n)
		for i := range dist {
			dist[i] = -1
		}
		q := make([]int, 0, n)
		dist[0] = 0
		q = append(q, 0)
		color := make([]int, n)
		for i := range color {
			color[i] = -1
		}
		color[0] = 0
		isBipartite := true
		for len(q) > 0 {
			u := q[0]
			q = q[1:]
			for _, v := range adj[u] {
				if dist[v] == -1 {
					dist[v] = dist[u] + 1
					color[v] = color[u] ^ 1
					q = append(q, v)
				} else {
					if color[v] == color[u] {
						isBipartite = false
					}
				}
			}
		}

		ans := make([]byte, n)
		if isBipartite {
			maxEven := 0
			maxOdd := 0
			if cntOdd%2 == 0 {
				maxEven = sumA
				if cntOdd > 0 {
					maxOdd = sumA - minOdd
				} else {
					maxOdd = -1
				}
			} else {
				maxOdd = sumA
				maxEven = sumA - minOdd
			}
			for i := 0; i < n; i++ {
				d := dist[i]
				if d == -1 {
					ans[i] = '0'
					continue
				}
				if d == 0 {
					ans[i] = '1'
					continue
				}
				if d%2 == 0 {
					if maxEven >= d {
						ans[i] = '1'
					} else {
						ans[i] = '0'
					}
				} else {
					if maxOdd >= d {
						ans[i] = '1'
					} else {
						ans[i] = '0'
					}
				}
			}
		} else {
			L := 4 * n
			if L < 0 {
				L = 0
			}
			size := (L + 64) / 64
			bs := make([]uint64, size)
			bs[0] = 1
			freq := make(map[int]int)
			for _, v := range A {
				freq[v]++
			}
			for v, c := range freq {
				k := 1
				for c > 0 {
					take := k
					if take > c {
						take = c
					}
					shift := v * take
					if shift > L {
						shift = L
					}
					// bs |= bs << shift
					wordShift := shift / 64
					bitShift := shift % 64
					if bitShift == 0 {
						for i := size - 1; i >= wordShift; i-- {
							bs[i] |= bs[i-wordShift]
						}
					} else {
						for i := size - 1; i > wordShift; i-- {
							bs[i] |= bs[i-wordShift] << uint(bitShift)
							bs[i] |= bs[i-wordShift-1] >> uint(64-bitShift)
						}
						bs[wordShift] |= bs[0] << uint(bitShift)
					}
					// mask
					if L%64 != 0 {
						bs[size-1] &= (1 << uint(L%64)) - 1
					} else {
						bs[size-1] = 0
						for i := size; i < len(bs); i++ {
							bs[i] = 0
						}
					}
					c -= take
					k <<= 1
				}
			}
			// Preprocess lists
			evens := make([]int, 0)
			odds := make([]int, 0)
			for s := 0; s <= L; s++ {
				word := s / 64
				bit := uint(s % 64)
				if bs[word]&(1<<bit) != 0 {
					if s%2 == 0 {
						evens = append(evens, s)
					} else {
						odds = append(odds, s)
					}
				}
			}
			// Precompute max_sum_p
			maxEven := -1
			maxOdd := -1
			if len(evens) > 0 {
				maxEven = evens[len(evens)-1]
			}
			if len(odds) > 0 {
				maxOdd = odds[len(odds)-1]
			}
			if cntOdd%2 == 0 {
				if sumA > maxEven {
					maxEven = sumA
				}
			} else {
				if sumA-minOdd > maxEven {
					maxEven = sumA - minOdd
				}
			}
			if cntOdd%2 == 1 {
				if sumA > maxOdd {
					maxOdd = sumA
				}
			} else {
				if cntOdd > 0 && sumA-minOdd > maxOdd {
					maxOdd = sumA - minOdd
				}
			}

			for i := 0; i < n; i++ {
				d := dist[i]
				if d == -1 {
					ans[i] = '0'
					continue
				}
				if d == 0 {
					ans[i] = '1'
					continue
				}
				p := d % 2
				// Check if there is sum in [d, L] with parity p
				found := false
				if p == 0 {
					// binary search in evens for lower_bound(d)
					idx := lowerBound(evens, d)
					if idx < len(evens) && evens[idx] <= L {
						found = true
					}
				} else {
					idx := lowerBound(odds, d)
					if idx < len(odds) && odds[idx] <= L {
						found = true
					}
				}
				if found {
					ans[i] = '1'
					continue
				}
				// Check if max_sum_p >= d (sum > L)
				if p == 0 {
					if maxEven >= d {
						ans[i] = '1'
						continue
					}
				} else {
					if maxOdd >= d {
						ans[i] = '1'
						continue
					}
				}
				ans[i] = '0'
			}
		}
		fmt.Fprintln(out, string(ans))
	}
}

func lowerBound(arr []int, target int) int {
	lo, hi := 0, len(arr)
	for lo < hi {
		mid := (lo + hi) / 2
		if arr[mid] < target {
			lo = mid + 1
		} else {
			hi = mid
		}
	}
	return lo
}
```