牛可乐有 n 个一次函数，第 i 个函数为 。 牛可乐有 m 次操作，每次操作为以下二者其一： • 将 修改为 。 • 求 。 牛可乐当然(bu)会做啦，他想考考你—— 答案对 取模。

输入描述:

第一行，两个正整数 n,m 。第二行，n 个整数  。第三行，n 个整数 。接下来 m 行，每行一个操作，格式见上。保证 ，。

输出描述:

对于每个求值操作，输出一行一个整数，表示答案。