Search on same page with pagination and pretty url

Hi

I have custom post type called store.
I have created one page domain.com/stores and I am listing all store(custom post type) posts on this page. I have also a search box on ‘stores’ page.

When I search for anything, It shows ‘store’ posts with the url like domain.com/stores?search=xyz. So how can I rewrite this url to make it pretty like domain.com/stores/search/xyz. Also I want to paginate the search results.

I tried couple of forums but couldn’t get the answer.

Any help would be appreciated.

Thank you