Lưu ý: Đọc input, output từ stdin/stdout

Spir là robot tự hành được trung tâm vũ trụ NAS phóng lên để thám hiểm bề mặt sao Hỏa. Spir được trang bị một tấm pin năng lượng mặt trời dưới dạng một bảng gồm ~m~ hàng và ~n~ cột, mỗi ô là một miếng pin hình vuông. Các hàng được đánh số từ trên xuống dưới lần lượt là ~1~, ~2~, ..., ~m~. Các cột được đánh số từ trái sang phải lần lượt là ~1~, ~2~, ..., ~n~. Tại thời điểm ban đầu lúc phóng lên, miếng pin tọa độ ~(i,j)~ ở hàng ~i~ cột ~j~ được thiết lập mức hấp thụ là ~a_{ij}~. Mức hấp thụ của mảng pin hình chữ nhật bất kì nằm trong tấm pin bằng tổng mức hấp thụ của các miếng pin trong mảng đó. Các miếng pin có thể điều khiển để thay đổi mức hấp thụ, do đó mức hấp thụ của cùng một mảng pin hình chữ nhật có thể thay đổi theo các thời điểm khác nhau.

NAS thiết kế 2 lệnh điều khiển R và D để điều chỉnh mức hấp thụ của các miếng pin. Khi nhận một lệnh R, đồng loạt mỗi miếng pin sẽ được thiết lập sang mức hấp thụ ngay trước khi nhận lệnh này của miếng pin liền kề bên phải cùng hàng. Mỗi miếng pin cuối hàng được thiết lập sang mức hấp thụ của miếng pin đầu hàng đó. Khi nhận một lệnh D, đồng loạt mỗi miếng pin sẽ được thiết lập sang mức hấp thụ ngay trước khi nhận lệnh này của miếng pin liền kề bên dưới cùng cột. Mỗi miếng pin ở cuối cột được thiết lập sang mức hấp thụ của miếng pin đầu cột đó.

Để điều khiển tấm pin của Spir, các kỹ sư NAS sử dụng các tín hiệu điều khiển chứa ~2~ số nguyên ~x~, ~y~ tương ứng với số lượng lệnh R và lệnh D cần áp dụng. Khi nhận được tín hiệu điều khiển, từng lệnh trong ~x~ lệnh R và sau đó từng lệnh trong ~y~ lệnh D sẽ tuần tự được thực hiện. Chú ý rằng trạng thái của tấm pin thu được sau tác động của mỗi lệnh là trạng thái tác động của lệnh kế tiếp. Trạng thái của tấm pin thu được sau mỗi tín hiệu điều khiển là trạng thái tác động của lệnh đầu tiên trong tín hiệu điều khiển tiếp theo.

Yêu cầu: Hãy giúp các kỹ sư NAS tính toán mức hấp thụ của mảng pin hình chữ nhật mà họ quan tâm tại một số thời điểm.

Input

• Dòng thứ nhất chứa hai số nguyên dương ~m~ và ~n~ lần lượt là số hàng và số cột của tấm pin;
• Dòng thứ ~i~ trong số ~m~ dòng tiếp theo chứa ~n~ số nguyên dương ~a_{ij}~ ~(a_{ij} \leq 1000~, ~j=~ ~1~, ~2~, ..., ~n)~ là mức hấp thụ được thiết lập lúc ban đầu của các miếng pin trên hàng thứ ~i~;
• Dòng tiếp theo chứa một số nguyên dương ~q~ là số lần gửi tín hiệu điều khiển hoặc yêu cầu tính toán của NAS;
• Mỗi dòng trong ~q~ dòng tiếp theo có cấu trúc như sau:
  • Đầu tiên là một số nguyên ~p~ ~(0 \leq p \leq 1)~;
  • Nếu ~p=0~, tiếp theo là hai số nguyên ~x~, ~y~ ~(0 \leq x, y \leq 1000)~ mô tả một tín hiệu điều khiển;
  • Nếu ~p=1~, tiếp theo là bốn số nguyên ~u~, ~v~, ~s~, ~t~ ~(1 \leq u \leq s \leq m~, ~1 \leq v \leq t \leq n)~ mô tả tọa độ mảng pin hình chữ nhật được yêu cầu tính toán, trong đó ~(u, v)~ là tọa độ ô góc trên bên trái và ~(s, t)~ tọa độ ô góc dưới bên phải.

Các số trên cùng một dòng cách nhau bởi dấu cách.

Output

In ra mức hấp thụ của các mảng pin hình chữ nhật tại từng thời điểm được yêu cầu tính toán tương ứng trong dữ liệu vào, mỗi số trên một dòng.

Scoring

• Có ~40\%~ số test ứng với ~40\%~ số điểm của bài thỏa mãn điều kiện: ~m~, ~n\leq 100~, ~q \leq 1000~ và ~p~ luôn bằng ~1~;
• ~30\%~ số test khác ứng với ~30\%~ số điểm của bài thỏa mãn điều kiện: ~m~, ~n\leq 100~, ~q \leq 1000~;
• ~30\%~ số test còn lại ứng với ~30\%~ số điểm của bài thỏa mãn điều kiện: ~m~, ~n\leq 500~, ~q \leq 5 \times 10^4~.

Sample Input

4 5
1 2 5 2 1
4 3 1 2 3
2 3 5 3 1
3 2 1 1 5
5
0 2 1
1 2 2 3 4
0 2 4
1 1 1 1 1
1 3 2 4 5

Sample Output

15
3
17

Giải thích

Trạng thái tấm pin sau mỗi tín hiệu điều khiển được thể hiện trên hình vẽ dưới đây. Các mảng pin hình chữ nhật cần tính toán được tô màu xám.

Lưu ý: Đọc input, output từ stdin/stdout

Một thành phố có ~N~ địa điểm được đánh số từ ~1~ đến ~N~, có ~M~ đoạn đường hai chiều, đoạn đường thứ ~i~ ~(1 \leq i \leq M)~ nối hai địa điểm ~u_i~, ~v_i~ ~(1 \leq u_i, v_i \leq N)~ với độ dài ~w_i~.

Nhóm bạn thân của Nam có ~K~ người đều sống trong thành phố, Nam được đánh chỉ số ~1~ và các bạn của Nam được đánh chỉ số lần lượt từ ~2~ đến ~K~. Ngày chủ nhật tới được nghỉ học, mỗi bạn trong nhóm sẽ chạy bộ đến công viên ưa thích của mỗi người để tập thể dục. Người thứ ~i~ ~(1 \leq i \leq K)~ có nhà nằm ở địa điểm ~a_i~ ~(1 \leq a_i \leq N)~ và chủ nhật sẽ tập thể dục ở công viên ưa thích nằm ở địa điểm ~b_i~ ~(1 \leq b_i \leq N)~. Để tiết kiệm thời gian, mỗi người sẽ xuất phát từ nhà đi tới công viên theo một đường đi có độ dài ngắn nhất.

Một đường đi gồm ~t~ địa điểm xuất phát từ địa điểm ~u~ và kết thúc tại địa điểm ~v~ là một chuỗi liên tiếp các địa điểm:

~u=c_1, c_2, ..., c_{t-1}, c_t= v~,

sao cho có đoạn đường nối trực tiếp giữa 2 địa điểm liên tiếp ~c_j~ và ~c_{j + 1}~ ~(1 \leq j < t)~ trong chuỗi. Độ dài của một đường đi là tổng độ dài của các đoạn đường nối trực tiếp 2 địa điểm liên tiếp trên đường đi đó.

Để việc tập thể dục trở nên vui vẻ hơn, Nam mong muốn có thể được đi chung với các bạn thân của mình trên đường đi tập thể dục. Nam được gọi là đi chung với một người bạn trên đoạn đường nối trực tiếp hai địa điểm ~u~ và ~v~ khi và chỉ khi đoạn đường này đều nằm trên đường đi tập thể dục của hai người và cả hai người đều đi đến địa điểm ~u~ tại cùng một thời điểm trước khi cùng nhau đi đến địa điểm ~v~. Gọi ~S~ là tổng độ dài của các đoạn đường mà Nam đi chung với ít nhất một người bạn thân của mình. Nam muốn giá trị của ~S~ là càng lớn càng tốt.

Chủ nhật, theo dự định, mỗi người đều sẽ xuất phát đi tập thể dục vào lúc ~7~ giờ sáng. Để có thể đạt được ~S~ là lớn nhất, Nam cố gắng thuyết phục mỗi người bạn thân của mình đi theo một đường đi ngắn nhất và xuất phát tại một thời điểm nào đó theo kế hoạch của Nam. Do đi theo đường đi có độ dài ngắn nhất nào cũng không làm thay đổi khoảng thời gian di chuyển trên đường nên tất cả đều đồng ý đi theo các lộ trình đường đi ngắn nhất mà Nam đề xuất. Tuy nhiên, việc thay đổi giờ xuất phát, trước hoặc sau ~7h~ sáng, có thể làm ảnh hưởng tới các kế hoạch cá nhân khác nên Nam chỉ thuyết phục được việc thay đổi thời gian xuất phát đối với những ai dễ tính mà thôi. Do đã quen với việc thức dậy sớm và xuất phát lúc ~7~ giờ sáng, Nam không thay đổi thời điểm xuất phát của mình.

Yêu cầu: Biết rằng để đi một đơn vị khoảng cách mất một đơn vị thời gian, biết danh sách những bạn dễ tính, hãy giúp Nam lên kế hoạch để đạt được ~S~ lớn nhất.

Input

• Dòng đầu tiên chứa ba số nguyên ~N~, ~M~ và ~K~ ~(1 \leq N \leq 10^ 5, 1 \leq M \leq 10^ 5,, 2 \leq K \leq 10)~;
• Dòng thứ ~i~ trong số ~M~ dòng tiếp theo chứa ba số nguyên ~u_i~, ~v_i~, ~w_i~ ~(1 \leq u_i, v_i \leq N, u_i \neq v_i, 1 \leq w_i \leq 10^9)~ mô tả đoạn đường hai chiều nối hai địa điểm ~u_i~ và ~v_i~ với độ dài ~w_i~. Dữ liệu đảm bảo luôn tồn tại đường đi giữa hai địa điểm bất kì và không có hai đoạn đường nào nối trực tiếp cùng một cặp địa điểm;
• Dòng tiếp theo chứa hai số nguyên ~a_1~ và ~b_1~ tương ứng là địa điểm xuất phát và địa điểm kết thúc đường đi tập của Nam;
• Dòng thứ ~i~ trong số ~K-1~ dòng tiếp theo, ~1 \le i \leq K-1~, chứa ba số nguyên ~p_{i+1}~, ~a_{i+1}~, ~b_{i+1}~ tương ứng là độ khó/dễ tính, địa điểm xuất phát và địa điểm kết thúc đường đi tập của người bạn có chỉ số ~i+1~, trong đó ~p_{i+1}~ bằng ~0~ nghĩa là khó tính và bằng ~1~ nếu dễ tính.

Các số trên cùng một dòng cách nhau bởi dấu cách.

Output

In ra 1 số nguyên duy nhất là giá trị lớn nhất của ~S~.

Scoring

• Có ~20\%~ số lượng test ứng với ~20\%~ số điểm của bài thỏa mãn điều kiện: ~K=2~, ~a_1=a_2~;
• ~20\%~ số lượng test khác ứng với ~20\%~ số điểm của bài thỏa mãn điều kiện: ~N \leq 100~, ~K=2~;
• ~30\%~ số lượng test khác ứng với ~30\%~ số điểm của bài thỏa mãn điều kiện: ~K=2~;
• ~20\%~ số lượng test khác ứng với ~20\%~ số điểm của bài thỏa mãn điều kiện: toàn bộ ~K-1~ người bạn là khó tính;
• ~10\%~ số lượng test còn lại ứng với ~10\%~ số điểm của bài thỏa mãn điều kiện: số người bạn dễ tính không quá ~5~.

Sample Input

7 8 4 
2 1 2
2 4 2
4 3 2
4 5 1
1 5 3
1 7 3
5 6 2
7 6 8
1 4
0 3 2
1 7 6
0 1 2 

Sample Output

3

Giải thích

Người thứ ~3~ xuất phát trước giờ dự kiến ~3~ đơn vị thời gian. Những người còn lại xuất phát đúng giờ dự kiến.

Lưu ý: Đọc input, output từ stdin/stdout

Một dãy các chữ số từ ~0~ đến ~9~ được gọi là dãy đối xứng nếu như đọc từ trái sang phải hay từ phải sang trái đều thu được kết quả giống nhau. Ví dụ như dãy rỗng và hai dãy ~010~, ~0110~ là các dãy đối xứng, còn các dãy ~123~, ~4449~ không phải là dãy đối xứng.

Với dãy ~S~ độ dài ~k~, các kí tự được đánh số từ ~1~ đến ~k~. Kí hiệu một dãy con của ~S~ gồm các kí tự liên tiếp từ vị trí ~a~ đến vị trí ~b~ là ~S(a, b)~ (giả thiết nếu ~a>b~ thì ~S(a, b)~ là dãy rỗng), dãy ~S~ được định nghĩa là dãy siêu đối xứng nếu đồng thời thỏa mãn các điều kiện sau:

• ~S(1, k)~ là dãy đối xứng;
• ~S(1, \left \lfloor k/2 \right \rfloor)~ là dãy đối xứng, trong đó kí hiệu ~\left \lfloor x \right \rfloor~ là số nguyên lớn nhất không vượt quá ~x~;
• ~S(k - \left \lfloor k/2 \right \rfloor + 1, k)~ là dãy đối xứng.

Ví dụ các dãy ~0~, ~11~, ~22322~, ~454454~ là các dãy siêu đối xứng, còn dãy ~990099~ không phải là dãy siêu đối xứng.

Một dãy được gọi là gần siêu đối xứng nếu như tồn tại một cách hoán đổi vị trí các phần tử của nó để thu được một dãy siêu đối xứng. Đương nhiên, một dãy siêu đối xứng cũng đồng thời là một dãy gần siêu đối xứng.

Một số nguyên dương ~d~ được gọi là số gần siêu đối xứng nếu như coi biểu diễn thập phân của nó như một dãy các chữ số từ ~0~ đến ~9~ (không có trường hợp dãy bắt đầu bởi chữ số ~0~) thì dãy biểu diễn đó là một dãy gần siêu đối xứng. Lưu ý là sau khi hoán đổi vị trí các phần tử, dãy thu được có thể bắt đầu bởi chữ số ~0~. Ví dụ, ~d=9505000~ là số gần siêu đối xứng vì tồn tại một cách hoán đổi vị trí các phần tử của dãy các chữ số biểu diễn d thành một dãy siêu đối xứng ~0509050~.

Yêu cầu: Cho hai số nguyên dương ~p~ và ~q~ ~(p \leq q)~, hãy tìm số lượng các số nguyên gần siêu đối xứng nằm trong khoảng từ ~p~ đến ~q~ (khoảng bao gồm cả ~p~ và ~q~).

Input

Hai số nguyên ~p~ và ~q~ cách nhau bởi dấu cách.

Output

In ra duy nhất một số là phần dư của số lượng số gần siêu đối xứng tìm được trong phép chia cho ~10^9+7~.

Scoring

• Có ~20\%~ số lượng test ứng với ~20\%~ số điểm của bài thỏa mãn điều kiện: ~1 \leq p \leq q \leq 10^5~;
• ~30\%~ số lượng test khác ứng với ~30\%~ số điểm của bài thỏa mãn điều kiện: ~p=10^{k-1}~, ~q=10^k-1~, ~2 \leq k \leq 18~;
• ~30\%~ số lượng test khác ứng với ~30\%~ số điểm của bài thỏa mãn điều kiện: ~1 \leq p \leq q \leq 10^{18}~;
• ~20\%~ số lượng test còn lại ứng với ~20\%~ số điểm của bài thỏa mãn điều kiện: ~1 \leq p \leq q \leq 10^{50000}~.

Sample Input 1

1 100

Sample Output 1

19

Sample Input 2

3111120 3111125 

Sample Output 2

2

Giải thích

• Ở ví dụ thứ nhất, các số gần siêu đối xứng là ~1~, ~2~, ~3~, ~4~, ~5~, ~6~, ~7~, ~8~, ~9~, ~11~, ~22~, ~33~, ~44~, ~55~, ~66~, ~77~, ~88~, ~99~, ~100~.
• Ở ví dụ thứ hai, hai số gần siêu đối xứng là ~3111122~ và ~3111123~.