Bola dan Gelas

Menuju acara 17-an, Pak Dengklek mempersiapkan permainan untuk perlombaan di desanya. Permainan tersebut adalah permainan yang klasik dan kini Pak Dengklek ingin mengujinya kepada Anda. Terdapat N (1 ≤ N ≤ 100.000) buah gelas yang diletakkan terbalik lalu dijejerkan di atas meja dan diberi nomor berbeda-beda antara 1 sampai N. Di dalam salah satu gelas terbalik tersebut diletakkan sebuah bola. Lalu dua buah gelas dipilih secara acak dan ditukar posisi dan nomornya. Pemilihan dan pertukaran tersebut dilakukan sebanyak M (1 ≤ M ≤ 100.000) kali. Setelah itu, semua gelas dibuka dan bola pastilah ditemukan di bawah salah satu gelas, misalnya gelas X.

Pak Dengklek ingin agar Anda menebak di gelas nomor berapakah bola tersebut berada pada awalnya. Tidak hanya sekali, Pak Dengklek ingin Anda menebak Q (1 ≤ Q ≤ 100.000) kali untuk beberapa kemungkinan X.

Format Masukan

Baris pertama berisi dua buah bilangan bulat N dan M. M baris berikutnya masing-masing berisi dua angka X1 dan X2, yang berarti gelas bernomor X1 ditukar nomor dan posisinya dengan gelas bernomor X2 (1 ≤ X1, X2 ≤ N). Baris berikutnya berisi bilangan Q, yang merupakan jumlah pertanyaan untuk kasus bersangkutan. Q baris berikutnya masing-masing berisi sebuah bilangan yang merupakan nomor gelas X (1 ≤ X ≤ N) tempat bola berada setelah permainan berakhir.

Format Keluaran

Q buah baris, masing-masing berisi jawaban untuk tiap pertanyaan yang diberikan di masukan.

Contoh Masukan

5 6
1 3
4 2
5 2
4 5
3 2
4 1
3
2
3
4

Contoh Keluaran

1
5
3 

So, the answer is :

 

Parkir Truk

Pak Dengklek memiliki 3 buah truk dan ingin memarkirkannya di tempat parkir yang memberikan harga sewa tempat parkir yang berbeda-beda tergantung dari banyaknya truk yang diparkir. Bila ada 1 truk, Pak Dengklek membayar A rupiah per menit. Bila ada 2 truk, untuk setiap truk Pak Dengklek membayar B rupiah per menit. Bila ada 3 truk, untuk setiap truk Pak Dengklek membayar C rupiah per menit.
Diberikan A, B, dan C (1 ≤ C ≤ B ≤ A ≤ 100) beserta interval waktu Pak Dengklek memarkirkan truk-truknya, tentukan berapa rupiah yang harus Pak Dengklek bayar.

Format Masukan

Baris pertama berisi 3 buah bilangan bulat A, B dan C. Tiga baris berikutnya masing-masing berisi dua bilangan bulat: awal dan akhir yang menyatakan waktu truk yang bersangkutan mulai diparkir dan meninggalkan tempat parkir. Rentang waktu ini adalah 1..100 dalam satuan menit.

Format Keluaran

Sebuah baris berisi sebuah bilangan bulat yang menyatakan total biaya parkir yang harus Pak Dengklek bayar.

Contoh Masukan

5 3 1
1 6
3 5
2 8

Contoh Keluaran

33 

So, the answer is :

 

Perkalian Pak Dengklek

Pak Dengklek bosan mengalikan pasangan bilangan dengan cara biasa, sehingga ia memutuskan bahwa sejak sekarang, ia akan menggunakan cara perkalian yang berbeda. Cara perkalian Pak Dengklek adalah menjumlahkan perkalian dari semua pasang digit-digit bilangan A dan B. Misalnya, perkalian dari 123 dan 45 adalah 1 * 4 + 1 * 5 + 2 * 4 + 2 * 5 + 3 * 4 + 3 * 5 = 54.
Diberikan dua bilangan A dan B (1 ≤ A, B ≤ 1.000.000.000), tentukan hasil kalinya menurut cara Pak Dengklek.

Format Masukan

Baris pertama berisi dua buah bilangan bulat A dan B.

Format Keluaran

Sebuah baris berisi sebuah bilangan yaitu hasil perkalian A dan B dengan cara Pak Dengklek.

Contoh Masukan

123 45

Contoh Keluaran

54

So, the answer is :

 

Tinggi Kandang Susun

Selain bebek, Pak Dengklek berkeinginan memelihara kucing dan karena itu ia bermaksud membangun kandang untuk kucing-kucingnya. Harga tanah kini sangat mahal, Pak Dengklek tidak memiliki lahan yang cukup luas untuk membangun kandang berlantai satu, maka kandang susunlah solusi untuk tempat tidur N kucingnya (1 ≤ N ≤ 1.000.000). Namun dalam kasus ini, justru yang kita pedulikan adalah total tinggi dari kandang susun tersebut, bukan luasnya. Sekedar informasi, kucing-kucing Pak Dengklek adalah hewan yang rewel, mereka tidak ingin tempat tinggalnya lebih rendah dari batas yang sudah mereka tentukan.
Untuk tiap lantai kandang, Pak Dengklek hanya dapat memasukkan K (1 ≤ K ≤ 1.000.000) kucing secara berurutan, sehingga kucing 1 sampai K pasti akan berada di lantai pertama, kucing ke K+1 sampai 2K pasti akan berada di lantai kedua, dan seterusnya. Agar semua kucing senang, tinggi setiap lantai haruslah nilai maksimal dari batas yang ditentukan oleh kucing-kucing yang ada dalam lantai tersebut.
Tugas Anda kini adalah mencari berapa total tinggi dari kandang susun yang akan dibangun Pak Dengklek. Perlu diingat untuk alas dan atap dibutuhkan papan setebal 1 sentimeter, di antara kedua lantai pun ada sekat setebal 1 sentimeter dan tebal-tebal itu harus diperhitungkan juga dalam menentukan total tinggi kandang.

Format Masukan

Baris pertama berisi dua buah bilangan bulat N dan K. N baris berikutnya masing-masing berisi sebuah bilangan Ti (1 ≤ Ti ≤ 1.000.000) yang merupakan batas tinggi yang diinginkan oleh kucing ke-i, dalam sentimeter.

Format Keluaran

Sebuah baris berisi sebuah bilangan bulat yaitu total tinggi kandang susun yang akan Pak Dengklek bangun, dalam sentimeter.

Contoh Masukan 1

5 3
30
20
15
19
29

Contoh Keluaran 1

62

Contoh Masukan 2

2 2
2
2

Contoh Keluaran 2

4

Penjelasan

Pada contoh masukan 1, total tinggi = 62 = 30 + 29 + 1 (alas) + 1 (atap) + 1 (sekat lantai 1 dan lantai 2).

---

So, the answer is :

 

Runtuh

Runtuh adalah sebuah permainan yang bertujuan untuk membuat penuh satu baris dari sebuah papan menggunakan beberapa bangun yang disediakan. Jika sebuah baris penuh terisi maka baris tersebut akan dihilangkan dan sisa bangun di atasnya akan "diruntuhkan" satu demi satu turun melewati ruang yang telah kosong sampai menumpuk di atas bangun yang ada di bawahnya. Penumpukan yang terjadi dapat menghasilkan situasi seperti pada saat awal di atas yaitu terdapat baris-baris yang penuh terisi, yang selanjutnya akan dihilangkan lagi (setelah semua runtuh). Demikian berlangsung bisa berulang-ulang sampai tidak ada lagi baris yang penuh terisi.
Anda akan diberikan sebuah kondisi papan yang terdiri atas R (1 ≤ R ≤ 20) baris dan C (1 ≤ C ≤ 8) kolom dari suatu permainan ini untuk ditentukan kondisi akhirnya. Misalnya untuk papan seperti di bawah ini:

Kondisi papan setelah baris yang terisi penuh dihilangkan, akan menyisakan ruang kosong seperti di bawah ini:

Bangun-bangun yang terletak di atas baris terbawah yang dihilangkan akan diruntuhkan ke bawah sehingga kondisi papan setelah terjadi penurunan adalah seperti di bawah ini:

Dalam contoh di atas kebetulan keruntuhan hanya sekali saja. Namun, dalam beberapa kasus uji bisa aja terjadi keruntuhan berulang-ulang.

Format Masukan

Baris pertama berisi dua buah bilangan bulat R dan C. R baris berikutnya masing-masing berisi C buah karakter '0' atau '1'. Karakter '1' menandakan adanya bangun pada posisi tersebut.

Format Keluaran

R buah baris, masing-masing berisi C buah karakter yaitu kondisi akhir dari papan permainan tersebut.

Contoh Masukan

11 6
000000
000000
011100
110011
111111
111000
111111
111111
111001
001100
111011

Contoh Keluaran

000000
000000
000000
000000
000000
010000
111000
111001
111101
001110
111011

---

So, the answer is :