时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
牛可乐有 n 个一次函数，第 i 个函数为
%3Dk_i%5Ctimes%20x%2Bb_i)
。
牛可乐有 m 次操作，每次操作为以下二者其一：
•
求
%5Cright)%5Cright)%5Ccdots%5Cright)%5Cright))
。
牛可乐当然(bu)会做啦，他想考考你——
答案对
取模。
输入描述:
第一行，两个正整数 n,m 。
第二行，n 个整数 
。
第三行，n 个整数 
。
接下来 m 行，每行一个操作，格式见上。
保证 
，
。
输出描述:
对于每个求值操作，输出一行一个整数，表示答案。
示例1
输入
复制
2 3
1 1
1 0
1 2 114514 1919810
2 1 2
2 1 1