Mitsuami

本の紐が、組あります。全ての組の紐にはそれぞれ数 が書かれています。
個のクエリが次のように与えられます:

• L R … についてこの時、番目の組の、番目から番目の紐を反転させます。

例えば、 の場合、 の部分を反転させるので になります。

pura君は隣りあう つの紐を選んで位置を入れ替えることを繰り返して紐を反転させたいです。この操作だけで紐を反転できることは保証されています。
しかし、の紐との紐を入れ替える時に、に書かれた数に書かれた数　のコストがかかります。
pura君はこの操作で全ての組の紐をクエリ通りに入れ替えます。すべてのクエリを終えた後のコストの総和の最小値を出力してください。

• 入力はすべて整数

入力は以下の形式で標準入力から与えられます。

すべてのクエリを終えた後のコスト総和の最小値を標準出力に出力してください。 コストの総和の最小値は 以下になることが保証されています。

番目から 番目までを反転させるには、 番目と 番目を入れ替えればよいです。 この時にかかるコストは、コストコスト となり、 が答えです。

それぞれ と書かれた紐の組が、 つあります。クエリ通りに部分的に反転させ、それぞれ にしたいです。
一つ目のクエリは 本目と 本目を入れ替えれば達成されるのでコストは 、二つ目のクエリは 本目と 本目を入れ替えれば達成されるのでコストは になり、合計は です。
クエリごとに別のひもの組になっていることに注意してください。