实际难度：入门-

题目背景

请注意本题不寻常的空间设置

本题卡常严重!!!

图片是Mc某模组的“志向远方”地牢的截图

题目描述

给定一个函数 $f$ 是 $\{1,2,\dots,n\}$ 到自身的双射，表示一个排列。

要求维护一个长为 $n$ 的数组 $a$，支持两种操作：

1 l r k表示将 $a_{f(l)},a_{f(l+1)},a_{f(l+2)},\dots,a_{f(r-2)},a_{f(r-1)},a_{f(r)}$ 加上 $k$

2 l r表示询问 $a_l+a_{l+1}+\dots+a_r$

输入格式

第一行，有两个整数 $n~m$，$n$ 表示数组长度,$m$ 表示操作次数

第二行，$n$ 个整数，第 $i$ 个表示 $a_i$

第三行，$n$ 个整数，第 $i$ 个表示 $f(i)$

接下来 $m$ 行，表示每个操作

输出格式

对于每个 $2$ 操作，输出一行一个整数表示答案

输入输出样例 #1

输入 #1

1 2
1
1
1 1 1 1
2 1 1

输出 #1

2

说明/提示

$1\le n,m\le10^5$

$-5\times10^{6}\le a_i,k\le5\times10^{6}$

$1\le l\le r\le n$

本题满分200分

Subtask #1是sht测试std的，1分

Subtask #2是测试你代码对不对的，99分

Subtask #3是测试你代码时间复杂度优不优的，100分

数据在win11下生成，保证 $a_i$,$k$ 在其值域范围内随机生成。各测试点信息如下

保证各测试点时限>=std用时$\times1.2$

输入输出大小：

时限：

type: default
subtasks:
- time: 1000ms
  memory: 512MB
  score: 1
  if: []
  id: 1
  type: sum
  cases:
  - input: wyddl1.in
    output: wyddl1.out
  - input: wyddl2.in
    output: wyddl2.out
  - input: wyddl3.in
    output: wyddl3.out
- time: 5000ms
  memory: 512MB
  score: 99
  if: []
  id: 2
  type: min
  cases:
  - input: wyddl4.in
    output: wyddl4.out
  - input: wyddl5.in
    output: wyddl5.out
  - input: wyddl6.in
    output: wyddl6.out
  - input: wyddl7.in
    output: wyddl7.out
  - input: wyddl8.in
    output: wyddl8.out
  - input: wyddl9.in
    output: wyddl9.out
  - input: wyddl10.in
    output: wyddl10.out
- time: 1000ms
  memory: 10MB
  score: 100
  if: []
  id: 3
  type: min
  cases:
  - input: wyddl4.in
    output: wyddl4.out
    time: 450ms
  - input: wyddl5.in
    output: wyddl5.out
    time: 1500ms
  - input: wyddl6.in
    output: wyddl6.out
    time: 700ms
  - input: wyddl7.in
    output: wyddl7.out
    time: 1500ms
  - input: wyddl8.in
    output: wyddl8.out
    time: 1300ms
  - input: wyddl9.in
    output: wyddl9.out
    time: 1500ms
  - input: wyddl10.in
    output: wyddl10.out
    time: 1500ms