Joyful Waltz: Dancing Animals and Circle Energy

In spring, the warm sunlight fills the prairie as the little animals celebrate by holding a grand dance party. The highlight of the dance is the waltz. Initially, n animals stand in a circle holding hands: animal 1 holds animal 2 with its right hand, animal 2 holds animal 3, and so on, with animal n holding animal 1.

During the dance, the animals can change formations. In a formation change, two animals A and B perform the following: animal A releases its right hand (which was holding its clockwise neighbor) and animal B releases its left hand (which was held by its counterclockwise neighbor). Then, animal A and animal B link hands. Moreover, if the released hands belong to other animals, those animals also join together. This rearrangement may split one circle into two or merge two circles into one.

For example, suppose 10 animals are arranged in a circle. If the formation change is performed on animals 2 and 8, then after the operation the new edges become: 2 is now holding 8 with its right hand, and the animals that lost connections (animal 3 and animal 7) link together. This results in two new circles: one with animals 1-2-8-9-10 and the other with animals 3-4-5-6-7. A subsequent formation change between animals 2 and 6 (now from different circles) may merge the circles into one.

Each animal i has a happiness value \(H_i\) and an emotion value \(F_i\) (indicating how moved it is). When two distinct animals i and j are in the same circle of size \(t\), and animal i is located at the p-th position to the right of animal j (with the 1st position being the animal that j is directly holding), then they contribute a happiness energy of \((t-p)\times H_j\times F_i\). Note that during the dance the values \(H_i\) and \(F_i\) may change.

Initially the animals are arranged in order: animal 1, 2, …, n in a circle (with animal n’s right-hand neighbor being animal 1). Given a sequence of events (formation changes and updates to \(H_i\) and \(F_i\)), your task is to output the total happiness energy produced by all animals after each formation change event.

inputFormat

The first line contains two integers \(n\) and \(q\) (\(1 \le n, q \le 100\)), denoting the number of animals and the number of events.

The second line contains \(n\) integers: \(H_1, H_2, \dots, H_n\) representing the happiness values of the animals.

The third line contains \(n\) integers: \(F_1, F_2, \dots, F_n\) representing the emotion values of the animals.

Each of the following \(q\) lines describes an event. There are two types of events:

• 1 A B: A formation change between animals A and B (1-indexed). It is guaranteed that A and B are distinct.
• 2 i newH newF: An update event where the \(i\)th animal's values become newH and newF.

You should output the total happiness energy after each formation change event (type 1).

outputFormat

For each formation change event (type 1), output a single line containing the total happiness energy produced by all animals after that event.

sample

10 3
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 2 8
2 3 2 2
1 2 6

100
165