在异形工厂里，有一种叫“轮换器”的工具。使用一次轮换器可以将一个 01 串中长度恰好为 的子串循环移位，即将 替换为 或 。
给定长度为 的 01 串 。有 次询问，每次询问会给定 ，求最少需要使用多少次轮换器才能将 变为 。
从标准输入读入数据。
输入的第一行包含两个正整数 ，分别表示字符串 的长度和询问次数。
输入的第二行包含一个长度为 的 01 字符串 。
输入的第三行包含一个长度为 的 01 字符串 。
输入的第 () 行包括两个正整数 ，表示第 次询问。
输出到标准输出。
对于每次询问，输出一行一个整数表示使用轮换器的最少次数。特别地，若无论如何都无法将 变为 ，则输出 。
10 5 1010111000 1111000001 1 6 3 5 4 5 1 10 8 9
3 1 -1 5 0
对于第一次询问，一种可能的操作方式为：
对于所有测试数据，均有：
特殊性质 A：对于所有 ，均有 。
