题目描述

选取显像管的任意一个平面，一开始平面内有$n$个电子，初始速度分别为$v_i$ ，定义飘升系数为：\sum_{1≤i<j≤n}|v_i×v_j|^2。 电子的速度常常会发生变化。也就是说，有两种类型的操作： •$1\;p\;x\;y$将 改为 $(x，y)$； •$2\;l\;r$ 询问$[l，r]$这段区间内的电子的飘升系数。 答案对$20170927$取模即可。

输入

第一行两个整数$n,m$，表示电子个数和询次个数。 接下来$n$行, 每行两个整数 $x，y$ 表示 $v_i$。 接下来$m$行, 每行形如$1\;p\;x\;y$或$2\;l\;r$，分别表示两种操作。

输出

对于每个操作$2$，输出一行一个整数表示飘升系数对 $20170927$ 取模的值。

输入样例

9 5
13052925 5757314
9968857 11135327
13860145 3869873
6912189 3461377
2911603 7061332
6334922 7708411
5505379 5915686
6806727 588727
7603043 15687404
2 1 6
1 7 2602783 18398476
1 8 8636316 19923037
2 2 7
2 2 4

输出样例

18529202
963126
19167545

提示

【数据规模与约定】

测试点编号	n	m
1	≤100	≤100
2	≤500	≤500
3	≤1000	≤1000
4	≤5000	≤5000
5	≤10000	≤10000
6	≤50000	≤50000
7	≤100000	≤100000
8	≤500000	≤500000
9	≤1000000	≤1000000
10	≤1000000	≤1000000

对于100%的数据，$1≤n,m≤10^6,0≤x_i,y_i<20170927,1≤l_i≤r_i≤n$。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共5个测试点，非原站或官方原始数据。总分100分。