func licenseKeyFormatting(S string, K int) string {
	runes := preprocess(S)
	n := len(runes)
	if n == 0 {
		return ""
	}
	dash, cnt := n/K, n%K
	if n%K == 0 {
		dash--
		cnt = K
	}
	key := make([]rune, n+dash)
	for i, j := 0, 0; i < n+dash; i++ {
		if cnt == 0 {
			cnt = K
			key[i] = '-'
		} else {
			key[i] = runes[j]
			j++
			cnt--
		}
	}
	return string(key)
}

func preprocess(s string) []rune {
	runes := make([]rune, 0)
	for _, r := range s {
		if r != '-' {
			if 'a' <= r && r <= 'z' {
				r = rune(r - 32)
			}
			runes = append(runes, r)
		}
	}
	return runes
}