# 考验

## A. 数学题

# Background

* zzz给uuu出了道题：
* { 给你a,b,c,d,p,请求出
* $(\dfrac{a^b}{c^d}) \ Mod \ p$
* 假设一定能整除。}
* uuu才学了亿天编程，他一看就懵(hui)了，你能帮他回答出来吗？

# Format

## Input

a,b,c,d,p

## Output

ans

# Samples

```input1
9 2 3 2 5
```

```output1
4
```

# Limitation

1s, 1024KiB for each test case.$1≤a,b,c,d,p≤10^9, GCD(c, p) = 1$，p是质数，注意时限**20ms**，std的10倍



---

## B. 考验(1)

# Description

给你一个长度为n的数组a，有m次询问，每次给你一个区间(l,r)，请你求出a数组区间(l,r)里的最大值。

# Format

## Input

第一行两个正整数，n，m。第二行n个整数，表示数组a。后面m行，每行两个正整数，l，r。

## Output

m行。对于每次询问，输出答案。

# Samples

```input1
5 4
2 4 3 1 5
1 5
2 4
4 4
1 2
```

```output1
5
4
1
4
```

# Limitation

1s, 1024KiB for each test case.
对于40%的数据，$1≤n,m≤10^3$
对于100%的数据，$1≤l≤r≤n≤10^5，1≤m≤2*10^6$



---

## C. 考验(2)

# Description

给你一个长度为n的数组a，有m次操作，每次给你一个数字op，

* 若op=1，则再输入两个数l，r，请求出a数组区间(l,r)里的最大值。
* 若op=2，则再输入两个数x，k，表示将数组a的第x项修改为k。

# Format

## Input

第一行两个正整数，n，m。第二行n个整数，表示数组a。后面m行，每行3个正整数。

## Output

对于每一次op=1的操作，输出结果。

# Samples

```input1
5 6
2 4 3 1 5
1 1 5
1 2 4
1 4 4
1 1 2
2 5 0
1 1 5
```

```output1
5
4
1
4
4
```



# Limitation

对于40%的数据，$1≤n,m≤10^3$
对于100%的数据，$1≤l≤r≤n≤5*10^5，1≤m≤2*10^5$



---

## D. 光速幂

## 题目描述

* 小k认为**快速幂**还是不够快，于是想请你写一个**光速幂**
* 给你两个整数 $a,b$，求 $a^b \bmod 1e9+7$。

## 输入格式

输入只有一行两个整数，分别代表 $a,b$。

## 输出格式

输出一行一个字符串 `a^b mod 1000000007=s`，其中 $a,b$ 分别为题目给定的值， $s$ 为运算结果。

## 样例 #1

### 样例输入 #1

```
2 65
```

### 样例输出 #1

```
2^65 mod 1000000007=164688009
```

## 提示

**样例解释**

$2^{65} = 36893488147419103232$，$36893488147419103232 \bmod 1000000007 = 164688009$。

**数据规模与约定**

对于 $100\%$ 的数据，保证$0≤a,b≤10^{500000}，a+b>0$

* 提示：1000000007是质数，long long装得下 $1000000007^{2}$
* 注意时限**400ms**



---