Rectangle Partition

Statement

Goal

There is a rectangle of given width w and height h,

On the width side, you are given a list of measurements.
On the height side, you are given another list of measurements.

Draw perpendicular lines from the measurements to partition the rectangle into smaller rectangles.

In all sub-rectangles (include the combinations of smaller rectangles), how many of them are squares?

Example

w = 10
h = 5
measurements on x-axis: 2, 5
measurements on y-axis: 3

   ___2______5__________ 
  |   |      |          |
  |   |      |          |
 3|___|______|__________|
  |   |      |          |
  |___|______|__________|

Number of squares in sub-rectangles = 4 (one 2x2, one 3x3, two 5x5)

Input

Line 1: Integers w h countX countY, separated by space
Line 2: list of measurements on the width side, countX integers separated by space, sorted in asc order
Line 3: list of measurements on the height side, countY integers separated by space, sorted in asc order

Output

Line 1: the number of squares in sub-rectangles created by the added lines

Constraints

1 ≤ w, h ≤ 20,000
1 ≤ number of measurements on each axis ≤ 500

Example

Input

10 5 2 1
2 5
3

Output

Tags

Loops, Arrays

Difficulty

Easy

Test cases

Sample Test

Input

10 5 2 1 2 5 3

Output

Validator 1 Validator

Input

10 5 2 1 1 4 1

Output

Squarish Test

Input

9 9 2 2 3 6 3 6

Output

Validator 2 Validator

Input

9 9 2 2 2 6 2 8

Output

Bigger 1 Test

Input

200 100 20 10 11 25 26 29 30 40 44 56 65 71 87 98 100 108 130 149 153 161 173 179 1 11 16 17 19 37 38 53 65 69

Output

123

Validator 3 Validator

Input

100 200 15 20 13 14 15 16 20 22 28 37 42 49 62 80 84 91 97 5 9 54 64 68 78 81 90 99 100 101 112 141 159 163 167 180 187 193 194

Output

247

Bigger 2 Test

Input

800 1000 15 20 36 116 145 146 163 172 173 182 279 337 371 631 695 705 772 86 95 103 319 336 362 370 382 445 519 522 657 707 811 842 866 881 895 918 930

Output

Validator 4 Validator

Input

1000 900 15 20 31 133 329 412 510 602 632 699 762 782 822 866 912 921 952 161 296 299 337 357 415 483 497 561 625 628 637 656 702 705 736 748 805 831 872

Output

Lo-density 1 Test

Input

12000 13000 36 25 317 416 455 914 1333 1488 2216 2739 3070 3755 4012 4509 5008 5107 5408 5828 5836 5926 6339 6448 6707 7305 7497 7531 8175 9104 9518 9566 9570 9713 9831 10003 10062 10843 11216 11495 734 2236 2287 3240 4185 4215 4609 4787 5619 5874 6667 6744 7379 7936 8989 9645 9649 9664 10088 10103 10710 11062 11267 12932 12979

Output

Validator 5 Validator

Input

13000 13000 26 25 158 1279 1384 1825 2077 2584 4084 4699 4716 4776 5336 6295 7755 8301 8388 8470 8670 8841 8847 9009 9068 9142 10968 11635 12227 12708 256 312 475 1221 1346 1909 2359 2821 3517 3890 4103 4766 4826 5338 5387 7171 7682 7991 8165 10439 10441 11329 11474 12207 12657

Output

Lo-density 2 Test

Input

20000 19990 3 4 8393 13715 13752 7017 8582 16500 19518

Output

Validator 6 Validator

Input

19999 20000 4 5 965 1290 4136 12558 1877 4557 8401 15325 19511

Output

Hi-density 1 Test

Input

10000 9000 123 201 1 14 79 126 390 506 573 690 747 778 798 887 896 907 912 1026 1122 1172 1193 1223 1380 1557 1693 1759 1840 2050 2063 2279 2321 2332 2396 2468 2514 2664 2803 2813 2823 2886 2913 3131 3363 3426 3580 3583 3780 3979 3981 4014 4102 4198 4284 4355 4666 4693 4708 4718 4926 5055 5094 5121 5292 5298 5299 5372 5406 5532 5634 5800 5801 5835 5838 5851 5875 6183 6305 6358 6359 6433 6479 6589 6600 6609 6635 6766 6774 6906 6940 6957 6978 7004 7008 7086 7226 7413 7442 7525 7536 7573 7625 7693 7721 8004 8113 8252 8300 8303 8385 8390 8523 8526 8688 8733 8766 9027 9075 9170 9196 9198 9223 9331 9497 9910 9945 59 60 63 128 132 146 183 249 270 303 380 387 467 606 643 663 682 707 728 734 799 851 1019 1078 1105 1116 1122 1126 1167 1237 1327 1402 1436 1439 1635 1674 1718 1751 1817 1864 1865 1871 1921 1995 2001 2085 2089 2214 2274 2282 2399 2442 2443 2447 2564 2569 2577 2875 2937 2988 2992 3017 3121 3162 3202 3216 3226 3228 3259 3416 3426 3443 3475 3795 3852 3879 3920 3993 4038 4039 4052 4137 4207 4243 4248 4251 4270 4328 4346 4354 4369 4379 4389 4396 4413 4426 4477 4491 4501 4508 4531 4533 4544 4659 4666 4720 4769 4846 4877 4977 5036 5143 5254 5348 5416 5425 5452 5468 5523 5580 5601 5611 5613 5620 5714 5722 5724 5748 5759 5794 5803 5927 5979 6042 6101 6115 6168 6177 6184 6230 6269 6336 6343 6416 6428 6709 6756 6786 6813 6895 6919 6945 6971 7099 7114 7142 7179 7241 7267 7381 7401 7412 7416 7422 7427 7456 7514 7519 7533 7555 7577 7597 7735 7739 7745 7777 7780 7859 7913 7917 7948 7984 7999 8000 8035 8051 8071 8143 8155 8228 8392 8480 8490 8575 8653 8677 8731 8754 8830 8867 8887

Output

22281

Validator 7 Validator

Input

9000 9000 122 221 260 378 384 389 401 431 474 529 642 750 768 786 855 923 956 977 1059 1080 1101 1274 1483 1526 1605 1732 1756 1794 1849 1885 1944 2047 2199 2224 2327 2367 2471 2475 2489 2523 2575 2616 2649 2656 2755 2848 2874 2885 3070 3085 3138 3206 3293 3423 3583 3630 3925 4055 4081 4154 4187 4353 4465 4554 4563 4786 4858 5042 5060 5100 5190 5212 5213 5270 5321 5344 5382 5384 5425 5439 5571 5670 5767 6060 6070 6120 6243 6266 6412 6445 6539 6610 6646 6692 6712 6754 6941 6962 7072 7150 7306 7316 7334 7477 7482 7653 7659 7704 7969 8036 8177 8198 8215 8239 8324 8379 8492 8575 8620 8662 8756 8763 8917 8951 64 70 74 109 350 447 465 471 529 585 606 634 704 712 736 737 758 817 856 883 915 927 949 995 1115 1164 1276 1306 1329 1367 1379 1430 1434 1472 1475 1503 1596 1661 1669 1674 1717 1729 1748 1772 1811 2019 2053 2095 2105 2138 2228 2331 2334 2370 2393 2398 2486 2494 2502 2530 2558 2586 2595 2597 2632 2634 2642 2666 2676 2688 2703 2716 2822 2925 2956 2966 2981 3067 3098 3161 3172 3213 3224 3227 3237 3255 3260 3282 3349 3368 3393 3412 3450 3460 3490 3530 3534 3538 3542 3619 3755 3838 3849 3881 3916 3957 3958 4065 4210 4305 4361 4363 4442 4469 4477 4758 4759 4811 4812 4853 4955 4984 4986 5005 5216 5229 5276 5289 5406 5433 5443 5581 5682 5832 5843 5982 6025 6028 6065 6066 6097 6110 6137 6145 6181 6396 6402 6441 6488 6539 6618 6702 6739 6768 6770 6801 6805 6853 6912 6916 6951 6988 6991 7002 7017 7028 7175 7240 7257 7288 7318 7328 7339 7346 7364 7424 7490 7507 7540 7558 7570 7583 7589 7604 7605 7617 7642 7688 7712 7751 7853 7917 7984 8048 8064 8137 8414 8476 8480 8531 8576 8577 8590 8597 8607 8631 8635 8657 8687 8753 8754 8786 8801 8873 8879 8884 8885 8890 8924 8986 8994

Output

26910

Hi-density 2 Test

Input

20000 20000 180 180 90 117 306 744 954 1005 1327 1604 2099 2167 2244 2272 2350 2466 2758 2816 2829 2860 2963 3040 3202 3265 3298 3600 4055 4158 4159 4272 4308 4325 4382 4595 4857 4894 4953 4955 5091 5145 5193 5797 5812 5839 5899 5912 5963 6044 6142 6161 6703 6802 6869 6950 7025 7028 7217 7669 7748 7804 8018 8114 8118 8200 8203 8422 8683 8692 8697 8711 8806 8839 8927 9006 9189 9266 9382 9391 9516 9534 9630 9764 9791 9853 9881 10088 10121 10271 10317 10327 10550 10559 10624 10944 11005 11135 11212 11331 11393 11449 11490 11764 11804 11875 11909 12011 12045 12091 12159 12398 12453 12559 12621 12693 13144 13196 13205 13262 13275 13323 13538 13608 14153 14291 14346 14518 14520 14560 14689 14765 14957 15042 15082 15382 15477 15539 15586 15612 15630 15719 15805 16101 16142 16300 16379 16563 16580 16685 16774 16919 17010 17056 17470 17482 17512 17520 17709 17722 17782 17800 17829 17945 18048 18071 18181 18279 18330 18492 18554 18653 18906 18938 19279 19294 19339 19587 19590 19672 19695 19730 19854 19950 90 177 485 652 664 793 797 943 1151 1271 1506 1569 1650 1789 1906 2037 2077 2221 2241 2323 2354 2533 2588 2858 3039 3223 3360 3480 3483 3587 3635 3842 3919 3962 4356 4410 4563 4949 4997 5059 5074 5090 5175 5187 5256 5309 5354 5384 5848 5995 6374 6506 6516 6547 6563 6628 6632 6709 6910 6916 6947 6983 7203 7345 7602 7800 7844 7858 7955 8206 8213 8317 8400 8435 8488 8538 8580 8710 8813 8815 8887 8896 8913 9111 9124 9209 9317 9345 9350 9544 9593 9945 10125 10208 10225 10270 10522 10993 11014 11025 11118 11231 11481 11538 11742 11761 11856 11887 12078 12112 12325 12506 12601 12617 12620 12719 12763 12875 12917 13257 13403 13485 13488 13635 13727 13814 13863 13882 13921 13996 14027 14068 14139 14338 14410 14526 14563 14617 14620 14691 14763 14786 14978 15215 15730 15776 15941 15964 16094 16174 16182 16303 16309 16450 16458 16649 16703 17008 17143 17220 17330 17628 17877 18203 18390 18463 18486 18611 18692 18693 18729 18902 18978 19219 19299 19355 19373 19506 19520 19599

Output

18431

Validator 8 Validator

Input

20000 20000 180 180 198 368 389 393 427 526 573 718 813 889 1111 1170 1203 1422 1568 1569 1758 1797 1868 1889 2205 2319 2371 2375 2591 2664 2761 2954 3101 3108 3376 3379 3381 3505 3517 3575 3864 3890 4108 4132 4342 4393 4400 4453 4518 4939 5313 5422 5545 5559 5654 5694 5734 5756 5787 5930 5955 5972 5976 6049 6062 6090 6184 6283 6324 6361 6537 6763 6841 6894 7087 7109 7150 7154 7271 7394 7822 8140 8292 8451 8549 8591 8865 8896 8987 9022 9198 9233 9253 9528 9590 9788 9810 10115 10179 10330 10362 10409 10417 10536 10562 11404 11552 11582 11668 11716 11935 11966 12030 12059 12081 12202 12416 12432 12783 12832 12871 12898 12999 13067 13099 13206 13412 13490 13497 13545 13565 13799 14079 14119 14422 14563 14916 15074 15170 15215 15220 15233 15293 15373 15392 15468 15545 15804 15825 15970 16096 16149 16214 16245 16406 16481 16669 16839 16853 16925 17121 17137 17173 17188 17316 17372 17513 17900 18023 18100 18502 18643 18727 18857 18894 18921 18944 19013 19095 19101 19409 19449 19540 19744 56 112 301 402 470 492 507 897 948 962 1019 1048 1301 1495 1530 1581 1598 1690 1782 1828 1850 1936 2139 2314 2561 2710 2851 2854 2933 3142 3276 3434 3496 3542 3651 3655 3747 3902 4148 4318 4733 4734 4749 4819 5544 6018 6134 6150 6353 6396 6434 6647 6902 6927 6932 6962 7294 7448 7531 7707 7948 8007 8341 8407 8470 8663 9065 9131 9184 9238 9302 9386 9461 9498 9503 9601 10030 10105 10140 10368 10547 10581 10990 11217 11240 11815 11836 11844 11857 11931 11986 11991 11998 12007 12251 12327 12379 12506 12576 12596 12652 12734 12815 12917 13009 13031 13099 13209 13230 13339 13412 13535 13699 13715 13787 13844 13863 13891 14091 14095 14122 14205 14303 14433 14443 14550 14820 14901 14950 15093 15120 15188 15189 15218 15287 15366 15450 15531 15592 15633 15718 15768 15886 16239 16323 16458 16620 16652 16660 16662 16738 16931 17132 17454 17578 17607 17765 17927 17946 17995 18093 18118 18477 18588 18616 18849 18876 18889 18901 18952 18984 19170 19225 19316 19764 19776 19868 19886 19904 19913

Output

17552

Imbalance Test

Input

20000 20000 4 300 4217 9527 18150 18400 221 239 328 499 652 688 764 768 823 910 1133 1150 1151 1222 1268 1319 1512 1666 2002 2017 2022 2098 2217 2329 2395 2464 2492 2515 2628 2800 2873 2929 3026 3030 3063 3211 3253 3266 3330 3364 3396 3402 3456 3463 3588 3681 3779 3829 3853 3907 3975 3981 4061 4110 4112 4189 4264 4345 4369 4466 4558 4633 4685 4802 4818 4985 5018 5022 5088 5136 5241 5264 5302 5310 5325 5340 5462 5480 5592 5632 5660 5692 5785 5913 5932 6066 6149 6397 6411 6419 6524 6563 6790 6811 6830 6890 6924 6939 7009 7104 7140 7258 7302 7377 7408 7449 7800 7850 7871 7940 8022 8221 8235 8281 8305 8338 8399 8530 8703 8870 8902 8927 8955 8977 9037 9055 9066 9109 9133 9288 9293 9425 9553 9590 9724 9770 9781 9804 9823 9859 9933 9980 9981 10059 10179 10206 10211 10290 10378 10613 10680 10699 10731 10734 10806 10888 10946 10956 11006 11025 11058 11228 11349 11351 11362 11442 11522 11525 11552 11650 11659 11683 11707 12001 12007 12052 12120 12151 12174 12411 12419 12473 12574 12662 12757 12766 12769 12771 12790 12809 12826 12891 12893 12928 12941 13001 13012 13267 13350 13446 13555 13659 13790 13796 13808 13828 13904 13949 14016 14040 14070 14099 14122 14327 14329 14374 14424 14602 14624 14635 14798 14805 14865 14945 15039 15140 15144 15306 15308 15312 15363 15436 15465 15606 15640 15666 15692 15810 15870 16028 16031 16169 16255 16256 16337 16398 16430 16435 16452 16483 16487 16526 16598 16603 16647 16652 16757 16843 16852 16859 17108 17193 17227 17365 17502 17677 17694 17702 17749 17939 18041 18159 18171 18200 18278 18356 18362 18466 18475 18600 18752 18757 18814 18832 18878 18924 18996 19009 19038 19107 19199 19226 19291 19394 19396 19432 19599 19727 19810 19989

Output

Validator 9 Validator

Input

20000 20000 400 3 12 15 26 162 213 293 338 375 400 504 515 559 679 709 718 746 844 864 889 905 917 968 1046 1077 1079 1115 1135 1194 1246 1265 1429 1439 1474 1616 1625 1720 1807 1844 1900 1957 2019 2036 2050 2091 2108 2119 2168 2192 2200 2212 2228 2370 2429 2443 2449 2486 2490 2554 2560 2565 2578 2599 2610 2737 2974 3011 3055 3127 3196 3222 3277 3289 3389 3435 3585 3595 3604 3661 3669 3689 3699 3744 3819 3852 3873 3997 4036 4090 4093 4116 4153 4168 4174 4224 4314 4329 4352 4381 4410 4412 4511 4734 4776 4826 4853 4933 4951 4980 5050 5065 5110 5130 5150 5190 5295 5314 5323 5423 5430 5641 5648 5657 5659 5703 5754 5806 5810 5852 5876 6091 6103 6170 6186 6201 6295 6331 6385 6406 6458 6548 6621 6722 6723 6725 6733 6743 6767 6828 6833 6895 6982 7114 7260 7310 7317 7319 7320 7379 7401 7570 7632 7636 7708 7803 7852 7881 7888 7987 8044 8079 8081 8107 8121 8189 8256 8258 8354 8395 8412 8438 8474 8493 8588 8719 8732 8754 8810 8884 8933 8953 9022 9063 9145 9170 9211 9227 9343 9416 9511 9551 9580 9603 9658 9737 9793 9827 9957 9996 10057 10227 10275 10286 10329 10333 10336 10414 10548 10653 10716 10727 10828 10841 10874 11060 11113 11154 11161 11195 11209 11230 11244 11263 11372 11417 11445 11455 11498 11548 11599 11664 11730 11797 11813 11823 11855 11874 11881 11890 11899 11946 11951 11977 12000 12104 12170 12185 12191 12200 12218 12288 12338 12427 12460 12575 12578 12755 12803 12846 12859 12918 12931 12986 13016 13052 13075 13086 13101 13154 13233 13255 13306 13355 13499 13500 13649 13758 13862 13867 13916 13942 13949 14026 14095 14150 14225 14269 14307 14493 14499 14586 14605 14732 14748 14759 14765 14885 14913 15002 15015 15103 15133 15228 15488 15497 15575 15631 15664 15712 15746 15814 15823 15921 15961 16005 16058 16099 16109 16132 16182 16184 16222 16223 16236 16255 16290 16291 16333 16402 16432 16606 16617 16647 16659 16779 16912 16949 17021 17115 17151 17357 17617 17639 17665 17858 17909 17991 18082 18103 18111 18159 18187 18223 18224 18231 18239 18293 18326 18392 18405 18485 18593 18729 18759 18784 18789 18795 18928 18981 18987 19009 19014 19084 19139 19147 19176 19222 19268 19277 19332 19368 19412 19445 19487 19516 19583 19662 19872 19874 19954 19956 3257 6917 16251

Output

Solution language

Solution

Stub generator input